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 C {
static int n;
    public static void main(String [] args) throws IOException {
    	Scanner sc=new Scanner(System.in);
    	PrintWriter pw=new PrintWriter(System.out);
    	char []s=sc.nextLine().toCharArray();
    	Stack<Integer> open=new Stack();
    	n=s.length;
    	int []closes=new int [n];
    	for(int i=0;i<n;i++)
    	{	
    		closes[i]=-1;
    		if(s[i]=='(')
    			open.push(i);
    		else if(!open.isEmpty())
    			closes[i]=open.pop();
    	}
    	SegmentTree tree=new SegmentTree(closes);
    	int m=sc.nextInt();
    	query []queries=new query[m];
    	for(int i=0;i<m;i++)
    		queries[i]=new query(sc.nextInt()-1,sc.nextInt()-1,i);
    	int []ans=new int [m];
    	
    	Arrays.sort(queries);
    	for(query q:queries)
    		ans[q.idx]=tree.query(q.l, q.r);
    	for(int x:ans)
    		pw.println(x*2);
    	pw.close();
    	
  }
    static class query implements Comparable<query>
    {
    	int l,r,idx;
    	query(int a,int b,int c)
    	{
    		l=a;r=b;idx=c;
    	}
		@Override
		public int compareTo(query other) {
			return l-other.l;
		}
		public String toString (){
			return l+" "+r;
		}
    }
   static class SegmentTree
   {
	   int []a,close[],i;
	  
	   SegmentTree(int []b)
	   {
		   a=b;
		   i=new int [4*n];
		   close=new int [4*n][];
		   build(1,0,n-1);
	   }
	   int query(int l,int r)
	   {
		   return query(1,0,n-1,l,r);
	   }
	   int query(int node,int tl,int tr,int l,int r)
	   {
		   if(r<tl || tr <l)
			   return 0;
		   if(tl>=l && tr<=r)
		   {
			   while(close[node][i[node]]<l)
				   i[node]++;
			   return (close[node].length)-i[node]-1;
			   
		   }
		   else
		   {
			   int mid=tl+tr>>1;
		   		return query(2*node,tl,mid,l,r)+query(2*node+1,mid+1,tr,l,r);
		   }
	   }
	   void build(int node,int tl,int tr)
	   {
		   if(tl==tr)
		   {
			   close[node]=new int [2];
			   close[node][0]=a[tl];
			   close[node][1]=a.length;
		   }
		   else
		   {
			   int left=node<<1,right=left+1;
			   int mid=tl+tr>>1;
    			build(left,tl,mid);
    			build(right,mid+1,tr);
    			close[node]=new int [close[left].length+close[right].length-1];
    			int i=0,j=0;
    			for(int k=0;k<close[node].length-1;k++)
    				if(close[left][i]<close[right][j])
    					close[node][k]=close[left][i++];
    				else
    					close[node][k]=close[right][j++];
    			close[node][close[node].length-1]=n;
    			
		   }
	   }
   }
    static class Scanner {
        StringTokenizer st;
        BufferedReader br;
 
        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }
 
        public Scanner(FileReader s) {
            br = new BufferedReader(s);
        }
 
        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
 
        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
 
        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }
 
        public String nextLine() throws IOException {
            return br.readLine();
        }
       
    }
}