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.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.PrintWriter;
public class C380 
{
    static class SegmentTree
    {
        int n;
        int tree[][];
        int start[];
        int end[];
        int ref[]={0,0,0};
        public SegmentTree(char a[])
        {
            n=a.length-1;
            tree=new int[4*n+7][3];
            start=new int[4*n+7];
            end=new int[4*n+7];
            build(a,1,0,n);
        }
        void build(char a[],int node,int s,int e)
        {
            start[node]=s;
            end[node]=e;
            if(s==e)
            {
                if(a[s]=='(')
                    tree[node][1]=1;
                else 
                    tree[node][2]=1;
            }
            else
            {
                int mid=(s+e)/2;
                build(a,2*node,s,mid);
                build(a,2*node+1,mid+1,e);
                int t=Math.min(tree[2*node][1],tree[2*node+1][2]);
                for(int i=0;i<3;i++)
                    tree[node][i]=tree[2*node][i]+tree[2*node+1][i]-t;
                tree[node][0]+=3*t;
                
            }
        }
        
        int query(int l,int r)
        {
            return query(1,l,r)[0];
        }
        int[] query(int node,int l,int r)
        {
            if(start[node]>r||end[node]<l)
                return ref;
            if(start[node]>=l&&end[node]<=r)
                return tree[node];
            int leftValue[]=query(2*node,l,r);
            int rightValue[]=query(2*node+1,l,r);
            int ret[]=new int[3];
            int t=Math.min(leftValue[1],rightValue[2]);
            for(int i=0;i<3;i++)
                ret[i]=leftValue[i]+rightValue[i]-t;
            ret[0]+=3*t;
            return ret;
        }
    }
    static class Scanner
    {
        BufferedReader br;
        StringTokenizer tk=new StringTokenizer("");
        public Scanner(InputStream is) 
        {
            br=new BufferedReader(new InputStreamReader(is));
        }
        public int nextInt() throws IOException
        {
            if(tk.hasMoreTokens())
                return Integer.parseInt(tk.nextToken());
            tk=new StringTokenizer(br.readLine());
            return nextInt();
        }
        public long nextLong() throws IOException
        {
            if(tk.hasMoreTokens())
                return Long.parseLong(tk.nextToken());
            tk=new StringTokenizer(br.readLine());
            return nextLong();
        }
        public String next() throws IOException
        {
            if(tk.hasMoreTokens())
                return (tk.nextToken());
            tk=new StringTokenizer(br.readLine());
            return next();
        }
        public String nextLine() throws IOException
        {
            tk=new StringTokenizer("");
            return br.readLine();
        }
        public double nextDouble() throws IOException
        {
            if(tk.hasMoreTokens())
                return Double.parseDouble(tk.nextToken());
            tk=new StringTokenizer(br.readLine());
            return nextDouble();
        }
        public char nextChar() throws IOException
        {
            if(tk.hasMoreTokens())
                return (tk.nextToken().charAt(0));
            tk=new StringTokenizer(br.readLine());
            return nextChar();
        }
        public int[] nextIntArray(int n) throws IOException
        {
            int a[]=new int[n];
            for(int i=0;i<n;i++)
                a[i]=nextInt();
            return a;
        }
        public long[] nextLongArray(int n) throws IOException
        {
            long a[]=new long[n];
            for(int i=0;i<n;i++)
                a[i]=nextLong();
            return a;
        }
        public int[] nextIntArrayOneBased(int n) throws IOException
        {
            int a[]=new int[n+1];
            for(int i=1;i<=n;i++)
                a[i]=nextInt();
            return a;
        }
        public long[] nextLongArrayOneBased(int n) throws IOException
        {
            long a[]=new long[n+1];
            for(int i=1;i<=n;i++)
                a[i]=nextLong();
            return a;
        }
    
    
    }
    
    public static void main(String args[]) throws IOException
    {
        Scanner in=new Scanner(System.in);
        PrintWriter out=new PrintWriter(System.out);
        char c[]=in.next().toCharArray();
        SegmentTree st=new SegmentTree(c);
        int n=in.nextInt();
        for(int i=0;i<n;i++)
            out.println(st.query(in.nextInt()-1, in.nextInt()-1));
        out.close();
    }

}
