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 «()(())(())».
/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
public  class SegmentTree  
{
    
    //Fast I/O Class
    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; 
        } 
    }
    
     //End Of Fast I/O Class
    
    
    
    
    //segment trees
    
    
    
    
     int st_complete[];
      int st_opening[];
       int st_closing[];
     // The array that stores segment tree nodes 
  
    /* Constructor to construct segment tree from given array. This 
       constructor  allocates memory for segment tree and calls 
       constructSTUtil() to  fill the allocated memory */
    SegmentTree(char arr[], int n) 
    { 
        // Allocate memory for segment tree 
        //Height of segment tree 
        int x = (int) (Math.ceil(Math.log(n) / Math.log(2))); 
  
        //Maximum size of segment tree 
        int max_size = 2 * (int) Math.pow(2, x) - 1; 
       
       max_size = 4*n;
        st_complete = new int[max_size]; // Memory allocation 
         st_closing = new int[max_size];
          st_opening = new int[max_size];
        constructSTUtil(arr, 0, n - 1, 0); 
    } 
  
    // A utility function to get the middle index from corner indexes. 
    int getMid(int s, int e) { 
        return s + (e - s) / 2; 
    } 
  
    /*  A recursive function to get the sum of values in given range 
        of the array.  The following are parameters for this function. 
  
      st    --> Pointer to segment tree 
      si    --> Index of current node in the segment tree. Initially 
                0 is passed as root is always at index 0 
      ss & se  --> Starting and ending indexes of the segment represented 
                    by current node, i.e., st[si] 
      qs & qe  --> Starting and ending indexes of query range */
    int[] getSumUtil(int ss, int se, int qs, int qe, int si) 
    { 
        // If segment of this node is a part of given range, then return 
        // the sum of the segment 
        if (qs <= ss && qe >= se){ 
           int[] array = {st_complete[si] , st_opening[si] , st_closing[si]}; 
           return array;
        }
        // If segment of this node is outside the given range 
        if (se < qs || ss > qe){ 
            int[] array = {0,0,0}; 
            return array;
        }
        // If a part of this segment overlaps with the given range 
        int mid = getMid(ss, se); 
        int left[] =  getSumUtil(ss, mid, qs, qe, 2 * si + 1) ;
        int right[] = getSumUtil(mid + 1, se, qs, qe, 2 * si + 2); 
        
        
    //     st_complete[si] = st_complete[left] + st_complete[right] + Math.min(st_opening[left] , st_closing[right]);
    //   st_opening[si] = st_opening[left] + st_opening[right] - Math.min(st_opening[left] , st_closing[right]);
    //   st_closing[si] = st_closing[left] + st_closing[right] - Math.min(st_opening[left] , st_closing[right]);
        
        int completed = left[0] + right[0] + Math.min(left[1],right[2]);
        int open = left[1] + right[1] - Math.min(left[1],right[2]);
        int close = left[2] + right[2] - Math.min(left[1],right[2]);
        
         int[] array = {completed , open , close}; 
         return array;
    } 
  
  
   
  
    // Return sum of elements in range from index qs (quey start) to 
   // qe (query end).  It mainly uses getSumUtil() 
    int[] getSum(int n, int qs, int qe) 
    { 
        // Check for erroneous input values 
        if (qs < 0 || qe > n - 1 || qs > qe) { 
            System.out.println("Invalid Input"); 
            int[] array = {-1};
            return array; 
        } 
        return getSumUtil(0, n - 1, qs, qe, 0); 
    } 
  
    // A recursive function that constructs Segment Tree for array[ss..se]. 
    // si is index of current node in segment tree st 
    void constructSTUtil(char arr[], int ss, int se, int si) 
    { 
        // If there is one element in array, store it in current node of 
        // segment tree and return 
        if (ss == se) { 
           // st[si] = arr[ss]; 
            if(arr[ss]=='('){
              st_opening[si] = 1;
              st_closing[si]  = 0;
              st_complete[si]  = 0;
            }else{
               st_opening[si]  = 0;
              st_closing[si]  = 1;
              st_complete[si]  = 0; 
            }
            return;
            
        } 
  
        // If there are more than one elements, then recur for left and 
        // right subtrees and store the sum of values in this node 
        int mid = getMid(ss, se); 
     //   st[si] = constructSTUtil(arr, ss, mid, si * 2 + 1) +  constructSTUtil(arr, mid + 1, se, si * 2 + 2); 
      int left = si * 2 + 1;
      int right = si * 2 + 2;
      constructSTUtil(arr, ss, mid, left) ; //left
      constructSTUtil(arr, mid + 1, se, right); //right
     
       st_complete[si] = st_complete[left] + st_complete[right] + Math.min(st_opening[left] , st_closing[right]);
       st_opening[si] = st_opening[left] + st_opening[right] - Math.min(st_opening[left] , st_closing[right]);
       st_closing[si] = st_closing[left] + st_closing[right] - Math.min(st_opening[left] , st_closing[right]);
      
        
    } 
    
    
    
    
    
    
    
    //end of segment tree
    
    
    
    
    
    
    
    
    
    
    
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		FastReader sc = new FastReader(); 
		String str = sc.nextLine();
		int n = str.length();
		char[] arr = str.toCharArray();
	//build the segment trees	
	
	SegmentTree  tree = new SegmentTree(arr, n); 
	
		int t = sc.nextInt();
		for(int tc =1;tc<=t;tc++){
		    int l = sc.nextInt()-1;
		    int r = sc.nextInt()-1;
		    //query for l to r
		 int[] ans =  tree.getSum(n, l, r);
		    System.out.println(ans[0]*2);
	
		}
	}
}
