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

public class Round233Div1C {

	public static class brac{
		int pairs;
		int open;
		int close;
		public brac(int pairs,int open,int close) {
			this.pairs=pairs;
			this.open=open;
			this.close=close;
		}
	}
	
	public static void Build(brac[] tree,int start,int end,int index,String str) {
		if(start==end) {
			tree[index]=new brac(0,0,0);
			if(str.charAt(start)=='(') {
				tree[index].open=1;
			}else {
				tree[index].close=1;
			}
			return;
		}
		int mid=(start+end)>>1;
		Build(tree, start, mid, index*2, str);
		Build(tree, mid+1, end, index*2+1, str);
		brac left=tree[index*2];
		brac right=tree[index*2+1];
		int value = Integer.min(left.open,right.close);
		tree[index]=new brac(value+left.pairs+right.pairs,right.open+left.open-value,left.close+right.close-value);
	}

	public static brac Query(brac[] tree,int start,int end,int index,int i,int j) {
		if(i>end || j<start) {
			return new brac(0,0,0);
		}
		if(i<=start  && j>=end) {
			return tree[index];
		}
		int mid=(start+end)>>1;
		brac left = Query(tree, start, mid, index*2, i, j);
		brac right= Query(tree, mid+1, end, index*2+1, i, j);
		int value = Integer.min(left.open,right.close);
		return new brac(value+left.pairs+right.pairs,right.open+left.open-value,left.close+right.close-value);
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		out=new PrintWriter(new BufferedOutputStream(System.out));
		FastReader s=new FastReader();
		String str=s.next();
		brac[] tree=new brac[4*str.length()+1];
		Build(tree, 0, str.length()-1, 1, str);
		int q=s.nextInt();
		while(q-->0) {
			int left=s.nextInt()-1;
			int right=s.nextInt()-1;
			brac ans=Query(tree, 0, str.length()-1, 1,left, right);
			out.println(ans.pairs*2);
		}
		out.close();
	}

	public static PrintWriter out;
	
	public static class FastReader {
		BufferedReader br;
		StringTokenizer st;
		//it reads the data about the specified point and divide the data about it ,it is quite fast
		//than using direct 

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
			//InputStream reads the data and decodes in character stream
			//It acts as bridge between byte stream and character stream
		}

		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (Exception e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());//converts string to integer
		}

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

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

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (Exception e) {
				e.printStackTrace();
			}
			return str;
		}
	}
	
}
