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

public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
		solver.solve(1, in, out);
        out.close();
    }
	
	

    static class Task {
		int[][] tree;
		int ts;
		
		public int[] merge(int[] l,int[] r){
			int[] arr;
			int lv,rv,min;
			arr=new int[3];
			min=Math.min(l[0],r[2]);
			arr[1]=l[1]+r[1]+min;
			lv=l[0]-min;
			rv=r[2]-min;
			arr[0]=lv+r[0];
			arr[2]=l[2]+rv;
			return arr;
		}
		
		public int recur(int i,int s,int e,String str){
			if(s>e)
				return 0;
			else if(s==e){
				if(str.charAt(s)=='(')
					tree[i][0]=1;
				else
					tree[i][2]=1;
				return 0;
			}
			int lc,rc,mid;
			mid=(e-s)/2;
			lc=2*i+1;
			rc=2*i+2;
			recur(lc,s,s+mid,str);
			recur(rc,s+mid+1,e,str);
			tree[i]=merge(tree[lc],tree[rc]);
			return 0;
		}
		
		
		public int[] comLen(int i,int gs,int ge,int s,int e){
			int[] arr,left,right;
			
			if(s>ge || e<gs){
				arr=new int[3];
				return arr;
			}
			else if(gs<=s && e<=ge){
				return tree[i];
			}
			int lc,rc,mid;
			mid=(e-s)/2;
			lc=2*i+1;
			rc=2*i+2;
			left=comLen(lc,gs,ge,s,s+mid);
			right=comLen(rc,gs,ge,s+mid+1,e);
			arr=merge(left,right);
			return arr;
		}
		
		public int solve(int testNumber, InputReader in, PrintWriter out) {
			int n,q;
			int[] ans;
			String s;
			s=in.next();
			q=in.nextInt();
			n=s.length();
			ts=(int)Math.ceil((double)Math.log(n)/Math.log(2));
			ts=(int)Math.pow(2,ts+1)-1;
			tree=new int[ts][3];
			recur(0,0,n-1,s);
			for(int i=0;i<q;i++){
				ans=comLen(0,in.nextInt()-1,in.nextInt()-1,0,n-1);
				out.println(ans[1]*2);
			}
			return 0;
		}
	}
    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

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

    }
}