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 «()(())(())».
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author dipankar12
 */
import java.io.*;
import java.util.*;
public class r223c {
    void construct(int seg[][],char ar[],int start,int end,int node)
    {
        if(start==end)
        {
            if(ar[start]=='(')
                seg[node][1]=1;
            else
                seg[node][2]=1;
            return;
        }
        
        int mid=(start+end)/2;
        construct(seg,ar,start,mid,2*node+1);
        construct(seg,ar,mid+1,end,2*node+2);
        
        seg[node][0]=seg[2*node+1][0]+seg[2*node+2][0]+Math.min(seg[2*node+1][1], seg[2*node+2][2]);
        seg[node][1]=seg[2*node+1][1]+seg[2*node+2][1]-Math.min(seg[2*node+1][1], seg[2*node+2][2]);
        seg[node][2]=seg[2*node+1][2]+seg[2*node+2][2]-Math.min(seg[2*node+1][1], seg[2*node+2][2]);
    }
    r223c1 sum(int seg[][],int start,int end,int qstart,int qend,int node)
    {
        if(qstart>end||qend<start)
        {
            r223c1 ob=new r223c1();
            ob.total=0;
            ob.left=0;
            ob.right=0;
            return ob;
        }
        
        if(qstart<=start&&qend>=end)
        {
            r223c1 ob=new r223c1();
            ob.total=seg[node][0];
            ob.left=seg[node][1];
            ob.right=seg[node][2];
            return ob;
        }
        
        int mid=(start+end)/2;
        r223c1 ob1=sum(seg,start,mid,qstart,qend,2*node+1);
        r223c1 ob2=sum(seg,mid+1,end,qstart,qend,2*node+2);
        
        r223c1 ob3=new r223c1();
        ob3.total=ob1.total+ob2.total+Math.min(ob1.left, ob2.right);
        ob3.left=ob1.left+ob2.left-Math.min(ob1.left, ob2.right);
        ob3.right=ob1.right+ob2.right-Math.min(ob1.left, ob2.right);
        return ob3;
    }
    public static void main(String args[])
    {
        fastio in=new fastio(System.in);
        PrintWriter pw=new PrintWriter(System.out);

        char st[]=in.nextLine().toCharArray();
        int n=st.length;
        int seg[][]=new int[n*4][3];
        
        r223c ob=new r223c();
        ob.construct(seg, st, 0, n-1, 0);
        
        int m=in.nextInt();
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<m;i++)
        {
            int x=in.nextInt()-1;
            int y=in.nextInt()-1;
            r223c1 ob1=ob.sum(seg, 0, n-1, x, y, 0);
            sb.append(ob1.total*2+"\n");
        }
        pw.println(sb);
        pw.close();
    }

    static class fastio {
     
            private final InputStream stream;
            private final byte[] buf = new byte[8192];
            private int cchar, snchar;
            private SpaceCharFilter filter;
     
            public fastio(InputStream stream) {
                this.stream = stream;
            }
     
            public int nxt() {
                if (snchar == -1)
                    throw new InputMismatchException();
                if (cchar >= snchar) {
                    cchar = 0;
                    try {
                        snchar = stream.read(buf);
                    } catch (IOException e) {
                        throw new InputMismatchException();
                    }
                    if (snchar <= 0)
                        return -1;
                }
                return buf[cchar++];
            }
     
            public int nextInt() {
                int c = nxt();
                while (isSpaceChar(c)) {
                    c = nxt();
                }
                int sgn = 1;
                if (c == '-') {
                    sgn = -1;
                    c = nxt();
                }
                int res = 0;
                do {
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    res *= 10;
                    res += c - '0';
                    c = nxt();
                } while (!isSpaceChar(c));
                return res * sgn;
            }
     
            public long nextLong() {
                int c = nxt();
                while (isSpaceChar(c)) {
                    c = nxt();
                }
                int sgn = 1;
                if (c == '-') {
                    sgn = -1;
                    c = nxt();
                }
                long res = 0;
                do {
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    res *= 10;
                    res += c - '0';
                    c = nxt();
                } while (!isSpaceChar(c));
                return res * sgn;
            }
     
            public int[] nextIntArray(int n) {
                int a[] = new int[n];
                for (int i = 0; i < n; i++) {
                    a[i] = nextInt();
                }
                return a;
            }
     
            public String readString() {
                int c = nxt();
                while (isSpaceChar(c)) {
                    c = nxt();
                }
                StringBuilder res = new StringBuilder();
                do {
                    res.appendCodePoint(c);
                    c = nxt();
                } while (!isSpaceChar(c));
                return res.toString();
            }
     
            public String nextLine() {
                int c = nxt();
                while (isSpaceChar(c))
                    c = nxt();
                StringBuilder res = new StringBuilder();
                do {
                    res.appendCodePoint(c);
                    c = nxt();
                } while (!isEndOfLine(c));
                return res.toString();
            }
     
            public boolean isSpaceChar(int c) {
                if (filter != null)
                    return filter.isSpaceChar(c);
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
            }
     
            private boolean isEndOfLine(int c) {
                return c == '\n' || c == '\r' || c == -1;
            }
     
            public interface SpaceCharFilter {
                public boolean isSpaceChar(int ch);
            }
        }
    

}
class r223c1
{
    int total;
    int left;
    int right;
}
