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 Codechef
{
   static class SegmentNode
   {
     SegmentNode  left;
     SegmentNode  right;
     int start,end,a,b,c;// a- complete subsequence, b- opening bracket, c- closed bracket
     public SegmentNode(int l,int r,int a,int b,int c)
     {
           this.a = a;
           this.b = b;
           this.c = c;
           start  = l;
           end    = r;
           left   = null;
           right  = null;
     }
    }

	  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; 
        } 
    } 
    
    public static SegmentNode build(String s ,int start,int end) 
    {
        if(start==end)
        {
           return new SegmentNode(start,end,0,s.charAt(start)=='('?1:0,s.charAt(start)==')'?1:0);
        }
        
        SegmentNode root = new SegmentNode(start,end,0,0,0);
        int mid = (start+end)/2;
        
        root.left  = build(s,start,mid);
        root.right = build(s,mid+1,end);

        int a1 = (root.left).a ,b1 = (root.left).b, c1 = (root.left).c;
        int a2 = (root.right).a ,b2 = (root.right).b, c2 = (root.right).c;

        int t =  Math.min(b1,c2);
        root.a = a1+a2+t;
        root.b = b2+b1-t;
        root.c = c1+c2-t;

        return root;
    }
    public static int[] query(SegmentNode root,int l,int r) 
    {
        int[] ans = new int[3];
        if(root.end<l || root.start>r)
           return ans;

        if(root.start>=l && root.end<=r)
        {
           ans[0] = root.a;ans[1] = root.b;ans[2] = root.c;
           return ans;
        }
        
        int[] p1 = query(root.left,l,r);
        int[] p2 = query(root.right,l,r);

        int t = Math.min(p1[1],p2[2]);
        ans[0] = p1[0]+p2[0]+t;
        ans[1] = p2[1]+p1[1]-t;
        ans[2] = p1[2]+p2[2]-t;
        
        return ans;
    }
	public static void main (String[] args) throws java.lang.Exception
	{
		  FastReader s = new FastReader(); 
	 	   //int t = s.nextInt();
           StringBuffer str = new StringBuffer();
     
           String st = s.nextLine();
           int q = s.nextInt();
    
           SegmentNode root =  build(st,0,st.length()-1);

           while(q-->0)
           {
              int l = s.nextInt()-1;
              int r = s.nextInt()-1;
              int[] ans = query(root,l,r);
              str.append(2*ans[0]+"\n");
           }
		System.out.println(str);
	}
}
