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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;


public class E223 {
	public static void main(String[] args) {
		MyScanner scan = new MyScanner();
		PrintWriter out = new PrintWriter(System.out);
		
		String s = scan.next();
		SegmentTree st = new SegmentTree(s);
		int Q = scan.nextInt();
		for(int i = 0;i <Q;i++){
			out.println(st.query(scan.nextInt()-1, scan.nextInt()-1));
		}
		
		out.close();
	}
	private static class SegmentTree {
		int N, k;
		int[] a, o, c;
		static triple zero = new triple(0,0,0);
		public SegmentTree(String s){
			N = s.length();
			a = new int[4*N];
			o = new int[4*N];
			c = new int[4*N];
			k = (int)Math.ceil(Math.log(N)/Math.log(2));
			build(0, (1<<k)-1, 1, s);
		}
		private void build(int L, int R, int idx, String s){
			int size = R-L+1;
			if(size==1){
				if(L>=N)return;
				if(s.charAt(L)=='(')o[idx]++;
				else c[idx]++;
				return;
			}
			build(L, R-size/2, idx*2,s);
			build(L+(size+1)/2, R, idx*2+1,s);
			int t = Math.min(o[2*idx], c[2*idx+1]);
			a[idx] = a[2*idx]+a[2*idx+1]+2*t;
			o[idx] = o[2*idx]+o[2*idx+1]-t;
			c[idx] = c[2*idx]+c[2*idx+1]-t;
		}
		public int query(int L, int R){return query(L,R,0,(1<<k)-1, 1).a;}
		private triple query(int L, int R, int tL, int tR, int idx){
			if(tL>=L && tR<=R)return new triple(a[idx], o[idx], c[idx]);
			if(tL<L&&tR<L)return zero;
			if(tL>R&&tR>R)return zero;
			int size = tR-tL+1;
			triple l= query(L,R,tL,tR-size/2, idx*2);
			triple r = query(L,R,tL+(size+1)/2, tR, idx*2+1);
			int t = Math.min(l.o, r.c);
			return new triple(l.a+r.a+2*t, l.o+r.o-t, l.c+r.c-t);
		}
		private static class triple {
			int a, o, c; public triple(int a, int o, int c){this.a=a;this.o=o;this.c=c;}
		}
	}
	private static class MyScanner {
		BufferedReader br;
		StringTokenizer st;
		public MyScanner() {br = new BufferedReader(new InputStreamReader(System.in));}
		String next(){
			while(st==null||!st.hasMoreElements()){
				try{st = new StringTokenizer(br.readLine());}
				catch(IOException e){e.printStackTrace();}
			}return st.nextToken();
		}
		int nextInt() {return Integer.parseInt(next());}
		long nextLong(){return Long.parseLong(next());}
	}
}
