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();
	}
	nyoom in = new nyoom(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;
		}
	}

	class nyoom {
		BufferedReader br;
		StringTokenizer st;
		nyoom(InputStream i) {
			br = new BufferedReader(new InputStreamReader(i));
			st = new StringTokenizer("");
		}
		String next() throws Exception {
			if (st.hasMoreTokens())
				return st.nextToken();
			else
				st = new StringTokenizer(br.readLine());
			return next();
		}
		int nextInt() throws Exception {
			return Integer.parseInt(next());
		}
	}
}