Sereja has a bracket sequence s1, s2, ..., sn, or, in other words, a string s of length n, consisting of characters "(" and ")".

Sereja needs to answer m queries, each of them is described by two integers li, ri (1 ≤ li ≤ ri ≤ n). The answer to the i-th query is the length of the maximum correct bracket subsequence of sequence sli, sli + 1, ..., sri. Help Sereja answer all queries.

You can find the definitions for a subsequence and a correct bracket sequence in the notes.

Input

The first line contains a sequence of characters s1, s2, ..., sn (1 ≤ n ≤ 106) without any spaces. Each character is either a "(" or a ")". The second line contains integer m (1 ≤ m ≤ 105) — the number of queries. Each of the next m lines contains a pair of integers. The i-th line contains integers li, ri (1 ≤ li ≤ ri ≤ n) — the description of the i-th query.

Output

Print the answer to each question on a single line. Print the answers in the order they go in the input.

Examples

Input

())(())(())(
7
1 1
2 3
1 2
1 12
8 12
5 11
2 10


Output

0
0
2
10
4
6
6

Note

A subsequence of length |x| of string s = s1s2... s|s| (where |s| is the length of string s) is string x = sk1sk2... sk|x| (1 ≤ k1 < k2 < ... < k|x| ≤ |s|).

A correct bracket sequence is a bracket sequence that can be transformed into a correct aryphmetic expression by inserting characters "1" and "+" between the characters of the string. For example, bracket sequences "()()", "(())" are correct (the resulting expressions "(1)+(1)", "((1+1)+1)"), and ")(" and "(" are not.

For the third query required sequence will be «()».

For the fourth query required sequence will be «()(())(())».
import java.io.*;
import java.util.*;

public class c380 {
	public static void main(String[] args) throws Exception {
		new c380();
	}
	FastScanner in = new FastScanner(System.in);
	PrintWriter out = new PrintWriter(System.out);

	char[] seq;
	seg tree;
	int q;
	int[] trash = {0, 0, 0};

	c380() throws Exception {
		seq = in.next().toCharArray();
		tree = new seg(0, seq.length-1, seq);

		q = in.nextInt();
		for (int i = 0; i < q; i++) {
			int l = in.nextInt()-1;
			int r = in.nextInt()-1;
			out.println(2*tree.query(l, r)[0]);
		}
		out.close();
	}

	class seg {
		int l, m, r;
		int[] ans;
		seg L, R;
		seg (int ll, int rr, char[] seq) {
			l = ll; r = rr; m = (l+r)/2; 
			ans = new int[3];
			if (l == r) {
				if (seq[l] == '(')
					ans[1] = 1;
				else
					ans[2] = 1;
				return;
			}
			L = new seg(l, m, seq);
			R = new seg(m+1, r, seq);
			ans[0] = L.ans[0]+R.ans[0];
			ans[1] = L.ans[1]+R.ans[1];
			ans[2] = L.ans[2]+R.ans[2];
			int min = Math.min(L.ans[1], R.ans[2]);
			ans[0] += min;
			ans[1] -= min; 
			ans[2] -= min;
		}

		int[] query(int ll, int rr) {
			if (r < ll || rr < l)
				return trash;
			if (ll <= l && r <= rr)
				return ans;
			int[] lans = L.query(ll, rr);
			int[] rans = R.query(ll, rr);
			int min = Math.min(lans[1], rans[2]);
			int[] qans = new int[3];
			qans[0] = lans[0]+rans[0]+min;
			qans[1] = lans[1]+rans[1]-min;
			qans[2] = lans[2]+rans[2]-min;
			return qans;
		}
	}

static class FastScanner {
	private InputStream stream;
	private byte[] buf = new byte[1 << 20];
	private int curChar;
	private int numChars;

	public FastScanner(InputStream stream) {
		this.stream = stream;
	}

	public FastScanner(File f) throws FileNotFoundException {
		this(new FileInputStream(f));
	}

	void close() {
		try {
			stream.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	int read() {
		if (numChars == -1)
			throw new InputMismatchException();
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	boolean isEndline(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}

	public String next() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}

	public String nextLine() {
		int c = read();
		while (isEndline(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndline(c));
		return res.toString();
	}

	// Jacob Garbage

	public int[] nextIntArray(int N) {
		int[] ret = new int[N];
		for (int i = 0; i < N; i++)
			ret[i] = this.nextInt();
		return ret;
	}

	public int[][] next2DIntArray(int N, int M) {
		int[][] ret = new int[N][];
		for (int i = 0; i < N; i++)
			ret[i] = this.nextIntArray(M);
		return ret;
	}

	public long[] nextLongArray(int N) {
		long[] ret = new long[N];
		for (int i = 0; i < N; i++)
			ret[i] = this.nextLong();
		return ret;
	}

	public long[][] next2DLongArray(int N, int M) {
		long[][] ret = new long[N][];
		for (int i = 0; i < N; i++)
			ret[i] = nextLongArray(M);
		return ret;
	}

	public double[] nextDoubleArray(int N) {
		double[] ret = new double[N];
		for (int i = 0; i < N; i++)
			ret[i] = this.nextDouble();
		return ret;
	}

	public double[][] next2DDoubleArray(int N, int M) {
		double[][] ret = new double[N][];
		for (int i = 0; i < N; i++)
			ret[i] = this.nextDoubleArray(M);
		return ret;
	}

}


}