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.*;
import java.nio.charset.StandardCharsets;
import java.util.Arrays;
import java.util.stream.Stream;

/**
 * Created by yaroslav.ovcharenko on 12/20/16.
 */

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 8192*8)  ;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static String parenteses;
    private static int[] open;
    private static int[] closed;
    private static int[] summ;

    public static void main(String[] args) throws IOException {
        parenteses = nextStr();
        int n = nextInts()[0];
        int[][] requests = new int[n][2];
        for (int i = 0; i < n; i++) {
            int[] req = nextInts();
            requests[i][0] = req[0];
            requests[i][1] = req[1];
        }
//        System.out.println(parenteses);
//        System.out.println(Arrays.deepToString(requests));

        int maxn = getMAXN(parenteses.length());
        open = new int[maxn];
        closed = new int[maxn];
        summ = new int[maxn];

        buildTree(1,0, parenteses.length()-1);

        for (int i = 0; i < n; i++) {
            int[] req = requests[i];
//            System.out.println(Arrays.toString(req));
            int[] count = count(1, 0, parenteses.length() - 1, req[0]-1, req[1]-1);
//            System.out.println(Arrays.toString(count));
            System.out.println(count[0]-count[1]-count[2]);
        }

    }

    private static int[] count(int i, int l, int r, int gl, int gr) {
        if(l > gr || r < gl) return new int[]{0,0,0};
        if(l >= gl && r <= gr) return new int[]{summ[i], open[i], closed[i]};

        int ln = i<<1;
        int rn = (i<<1) + 1;
        int[] left = count(ln, l, (l+r)>>1, gl, gr);
        int[] right = count(rn, ((l+r)>>1) + 1, r, gl, gr);

        int unm = Math.min(left[1], right[2]);
        int s = left[0] + right[0];
        int o = left[1] - unm + right[1];
        int c = right[2] - unm + left[2];
        return new int[]{s,o,c};
    }

    private static void buildTree(int i, int l, int r) {
        if(l==r) {
            if(parenteses.charAt(l) == '(') {
                open[i]=1;
            } else {
                closed[i]=1;
            }
            summ[i]=1;
            return;
        }
        int ln = i<<1;
        int rn = (i<<1) + 1;
        buildTree(ln, l, (l+r)>>1);
        buildTree(rn, ((l+r)>>1) + 1, r);

        int unm = Math.min(open[ln], closed[rn]);
        summ[i] = summ[ln] + summ[rn];
        open[i] = open[ln] - unm + open[rn];
        closed[i] = closed[rn] - unm + closed[ln];
    }

    private static int getMAXN(int n) {
        return 1 + (int) Math.pow(2., 2. + (Math.log(n) / Math.log(2)));
    }

    private static int[] nextInts() throws IOException {
        return Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }

    private static String nextStr() throws IOException {
        return br.readLine();
    }
}