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.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;


public class SerejaAndBrackets{
	
	static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            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()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    }
	static class Pair
	{
		int to = 0;
		int tc = 0;
		int uo = 0;
		int uc = 0;
		int ans = 0;
	}
	static class SegmentTree
	{	
		char ar[];
		Pair pr[];
		
		SegmentTree(char ar[],int n)
		{	
			int height = (int)Math.ceil((double)Math.log(n)/Math.log(2));
			int maxSize = 2*(int)Math.pow(2,height)-1;
			pr = new Pair[maxSize];
			for(int i  = 0; i < pr.length; i++)
			{
				pr[i] = new Pair();
			}
			build(ar,0,0,n-1);
		}
		void build(char a[], int v, int tl, int tr) {
		    if (tl == tr) {
		    	if(a[tl] == '(')
		    	{	
		    		pr[v].to = 1;
		    		pr[v].uo = 1;
		    	}
		    	else
		    	{
		    		pr[v].tc = 1;
		    		pr[v].uc = 1;
		    	}
		    }
		    else {
		        int tm = (tl + tr) / 2;
		        build(a, v*2+1, tl, tm);
		        build(a, v*2+2, tm+1, tr);
		        pr[v].to = pr[v*2+1].to+pr[v*2+2].to;
		        pr[v].tc = pr[v*2+1].tc+pr[v*2+2].tc;
		        pr[v].ans = 2*Math.min(pr[v*2+1].uo, pr[v*2+2].uc)+pr[v*2+1].ans+pr[v*2+2].ans;
		        pr[v].uo = pr[v].to-(int)pr[v].ans/2;
		        pr[v].uc = pr[v].tc-(int)pr[v].ans/2;		    
		        }
		}
		
		Pair get(int v, int tl, int tr, int l, int r) {
		    if (l > r) 
		        return new Pair();
		    if (l == tl && r == tr) {
		        return pr[v];
		    }
		    int tm = (tl + tr) / 2;
		    Pair a = get(v*2+1, tl, tm, l, Math.min(r, tm));
		    Pair b = get(v*2+2, tm+1, tr, Math.max(l, tm+1), r);
		    Pair n = new Pair();
		    n.to = a.to+b.to;
	        n.tc = a.tc+b.tc;
	        n.ans = 2*Math.min(a.uo, b.uc)+a.ans+b.ans;
	        n.uo = n.to-(int)n.ans/2;
	        n.uc = n.tc-(int)n.ans/2;
		    return n;
		}
		
		/*void update(int v, int tl, int tr, int pos, int new_val) {
		    if (tl == tr) {
		        t[v] = new_val;
		    } else {
		        int tm = (tl + tr) / 2;
		        if (pos <= tm)
		            update(v*2, tl, tm, pos, new_val);
		        else
		            update(v*2+1, tm+1, tr, pos, new_val);
		        t[v] = t[v*2] + t[v*2+1];
		    }
		}*/
	}
	public static void main(String[] args) 
	{
		OutputStream outputStream = System.out;
        FastReader sc = new FastReader();
        PrintWriter out = new PrintWriter(outputStream);
        
        char ar[] = sc.nextLine().toCharArray();
        int n = ar.length;
        SegmentTree st = new SegmentTree(ar,n);
        
        int q = sc.nextInt();
        while(q-- > 0)
        {
        	int l = sc.nextInt()-1;
        	int r = sc.nextInt()-1;
        	out.println(st.get(0,0,n-1,l,r).ans);
        }
        out.close();
	}

}

