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.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Stack;
import java.util.StringTokenizer;
 public   class Main {
    static class Reader
    {
    BufferedReader r;
    StringTokenizer str;
    Reader()
    {
    r=new BufferedReader(new InputStreamReader(System.in));
    }
    Reader(String fileName) throws FileNotFoundException
    {
    r=new BufferedReader(new FileReader(fileName));
    }
    public String getNextToken() throws IOException
    {
    if(str==null||!str.hasMoreTokens())
    {
    str=new StringTokenizer(r.readLine());
    }
    return str.nextToken();
    }
    public int nextInt() throws IOException
    {
    return Integer.parseInt(getNextToken());
    }
    public long nextLong() throws IOException
    {
    return Long.parseLong(getNextToken());
    }
    public double nextDouble() throws IOException
    {
    return Double.parseDouble(getNextToken());
    }
    public String nextString() throws IOException
    {
    return getNextToken();
    }
    public int[] intArray(int n) throws IOException
    {
        int a[]=new int[n];
        for(int i=0;i<n;i++)
            a[i]=nextInt();
        
        return a;
        
    }
    public long[] longArray(int n) throws IOException
    {
        long a[]=new long[n];
        for(int i=0;i<n;i++)
            a[i]=nextLong();
        
        return a;
        
    }
    public String[] stringArray(int n) throws IOException
    {
        String a[]=new String[n];
        for(int i=0;i<n;i++)
            a[i]=nextString();
        
        return a;
        
    }
    public int gcd(int a, int b) {
if(b == 0){
return a;
}
return gcd(b, a%b);
}
    }
  
    static  int bits=32;
    public static void main(String args[]) throws IOException{
     
     
       Reader r=new Reader();
       PrintWriter pr=new PrintWriter(System.out,false);
       
       
       char a[]=r.nextString().toCharArray();
       int n=a.length;
      int m=r.nextInt();
     
      int tree[][]=new int[4*n][3];
     
     
      construct(a,tree,1,0,n-1);
      int x,y;long z;
      for(int i=0;i<m;i++)
      {
          x=r.nextInt()-1;
          y=r.nextInt()-1;
          
          pr.println(query(tree,1,0,n-1,x,y)[0]);
              
          
                  
          
      }
      
      
      
       pr.flush();
       pr.close();
    }
    
public static void construct(char a[],int tree[][], int root,int l ,int r)
{
    
    if(l==r)
    {
        
        tree[root][0]=0;
        if(a[l]=='(')
            tree[root][1]=1;
        else
            tree[root][2]=1;
        return;
    }
    construct(a,tree,root<<1,l,(l+r)>>1);
    construct(a,tree,(root<<1)+1,((l+r)>>1)+1,r);
    
    
    tree[root][0]+=tree[root<<1][0]+tree[(root<<1)+1][0]+2*(Math.min(tree[root<<1][1],tree[(root<<1)+1][2]));
    tree[root][1]+=tree[root<<1][1]+tree[(root<<1)+1][1]-Math.min(tree[root<<1][1],tree[(root<<1)+1][2]);
    tree[root][2]+=tree[root<<1][2]+tree[(root<<1)+1][2]-Math.min(tree[root<<1][1],tree[(root<<1)+1][2]);
    
  //  System.out.println(root+" "+stack[root]);
}



static int[] query(int tree[][],int root,int l,int r,int begin,int end)
{
    
    if(begin>r||end<l)
        return new int[]{0,0,0};
    if(begin<=l&&r<=end)
    {
        return tree[root];
        
        
    }
    
    return add(query(tree,root<<1,l,(l+r)>>1,begin,end),query(tree,(root<<1)+1,((l+r)>>1)+1,r,begin,end));
    
    
    
}
public static int[] add(int a[],int b[])
{
    int c[]=new int[3];
    
    c[0]=a[0]+b[0]+(2*Math.min(a[1],b[2]));
    c[1]=a[1]+b[1]-Math.min(a[1],b[2]);
    c[2]=a[2]+b[2]-Math.min(a[1],b[2]);
    
    return c;
}
 } 

