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.InputStreamReader;
import java.io.IOException;
import java.util.InputMismatchException;
import java.io.PrintStream;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Reader;
import java.io.Writer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Nipuna Samarasekara
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		FastScanner in = new FastScanner(inputStream);
		FastPrinter out = new FastPrinter(outputStream);
		TaskC solver = new TaskC();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskC {
   /////////////////////////////////////////////////////////////
    public void solve(int testNumber, FastScanner in, FastPrinter out) {
    String S=in.next();
      MaxSegmentTree mxs= new MaxSegmentTree(S.length(), S);
        int q=in.nextInt();
        for (int i = 0; i < q; i++) {
         //   System.out.println("------------ "+i);
          int ll=in.nextInt()-1,rr=in.nextInt();
         //   System.out.println( S.substring(ll,rr));                                    //  88


            reg ans= mxs.getMax(ll, rr);
            out.println(ans.pair*2);
        }


    }
}

class reg{
    int pair,toleft,toright;

    public String toString() {
        return "reg{" +
                "pair=" + pair +
                ", toleft=" + toleft +
                ", toright=" + toright +
                '}';
    }

    reg(int pair, int toleft, int toright) {
        this.pair = pair;
        this.toleft = toleft;
        this.toright = toright;
    }
    void add(int p, int l, int r){
     pair+=p;toleft+=l;toright+=r;

    }
}

class MaxSegmentTree {

    int n;
    String S;
    reg[] regs;
    public MaxSegmentTree(int n ,String S) {
        this.S=S;
        this.n = Integer.highestOneBit(n) << 1;

        regs = new reg[this.n * 2];
        for (int i = 0; i < regs.length; i++) {
            regs[i] = new reg(0,0,0);
        }
        for (int i = 0; i < n; i++) {
            set(i, i);
        }
    }

    public void set(int x, int y) {
        x += n;

        if(S.charAt(y)=='('){
        regs[x].add(0,1,0); }
        else  regs[x].add(0,0,1);

        while (x >= 1) {
            x >>= 1;
            reg left = regs[x << 1];
            reg right = regs[(x << 1) | 1];
           regs[x]= new reg(left.pair+right.pair+Math.min(left.toleft,right.toright),right.toleft+Math.max(0,left.toleft-right.toright),left.toright+Math.max(0,right.toright-left.toleft));


        }
    }



    public reg getMax(int left, int right) {
//        --right;
//        left += n;
//        right += n;
//        reg ret = new reg(0,0,0);
//        int size=1;
//        while (left <= right) {
//            if ((left & 1) == 1) {
//                ret.add(regs[left].pair + Math.min(ret.toright, regs[left].toleft) + Math.min(regs[left].toright, ret.toleft), Math.max(0, regs[left].toleft - ret.toright) - Math.min(regs[left].toright, ret.toleft), -Math.min(ret.toright, regs[left].toleft));
//                System.out.println(left+" ll "+ret+" "+size);
//
//                left++;
//
//
//            }
//            if ((right & 1) == 0) {
//
//                ret.add(regs[right].pair+Math.min(ret.toleft,regs[right].toright)+Math.min(regs[right].toleft,ret.toright),-Math.min(ret.toleft,regs[right].toright),Math.max(0,regs[right].toright-ret.toleft)-Math.min(regs[right].toleft,ret.toright));
//              //  System.out.println(regs[right]+" pppp" );
//                System.out.println(right+" rr "+ret+" "+size);
//
//                right--;
//            }
//            left >>= 1;
//            right >>= 1;
//            size*=2;
//        }

//     return ret;
        reg ret= new reg(0,0,0);
        int m2=0;
        int temp = left;
        int ss=1;
        if(temp!=0)
        while(temp%2==0){temp/=2;m2++;ss*=2;}
        while(true){
            while(left+ss>right){
                m2--;ss/=2;

            }
            reg cur= regs[(left+n)>>m2];
            // merge
         ret.add(cur.pair+Math.min(ret.toleft,cur.toright),cur.toleft-Math.min(ret.toleft,cur.toright),0);
            left+=ss;
            if(left==right)break;
            temp=left/(int)Math.pow(2,m2);
            while(temp%2==0){temp/=2;m2++;ss*=2;}

        }
        return ret;
    }

}

class FastScanner extends BufferedReader {

    public FastScanner(InputStream is) {
        super(new InputStreamReader(is));
    }

    public int read() {
        try {
            int ret = super.read();
//            if (isEOF && ret < 0) {
//                throw new InputMismatchException();
//            }
//            isEOF = ret == -1;
            return ret;
        } catch (IOException e) {
            throw new InputMismatchException();
        }
    }

    public String next() {
        StringBuilder sb = new StringBuilder();
        int c = read();
        while (isWhiteSpace(c)) {
            c = read();
        }
        if (c < 0) {
            return null;
        }
        while (c >= 0 && !isWhiteSpace(c)) {
            sb.appendCodePoint(c);
            c = read();
        }
        return sb.toString();
    }

    static boolean isWhiteSpace(int c) {
        return c >= 0 && c <= 32;
    }

    public int nextInt() {
        int c = read();
        while (isWhiteSpace(c)) {
            c = read();
        }
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int ret = 0;
        while (c >= 0 && !isWhiteSpace(c)) {
            if (c < '0' || c > '9') {
                throw new NumberFormatException("digit expected " + (char) c
                        + " found");
            }
            ret = ret * 10 + c - '0';
            c = read();
        }
        return ret * sgn;
    }

    public String readLine() {
        try {
            return super.readLine();
        } catch (IOException e) {
            return null;
        }
    }

    }

class FastPrinter extends PrintWriter {

    public FastPrinter(OutputStream out) {
        super(out);
    }

    public FastPrinter(Writer out) {
        super(out);
    }


}

