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.util.*;
import java.io.*;

public class Brackets {
    
    static int N;
    static int[] left;
    static int[] right;
    static int[] tree;
    public static void main(String[] args) throws Exception {
    BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
    String s = sc.readLine();
    /** build tree **/
    N = s.length();
    left = new int[N];
    right = new int[N];
    tree = new int[4*N];
    for (int i = 0; i < N; i++) {
        if (s.charAt(i) == '(') {
        if (i != 0) {
            right[i] += right[i-1];
            left[i] += left[i-1];
        }
        left[i]++;
        } else if (s.charAt(i) == ')') {
        if (i != 0) {
            left[i] += left[i-1];
            right[i] += right[i-1];
        }
        right[i]++;
        }
    }
    build(0, 0, N-1);
    /** answer queries **/
    int queries = Integer.parseInt(sc.readLine());
    StringBuilder br = new StringBuilder("");
    for (int i = 0; i < queries; i++) {
        String[] spl = sc.readLine().split(" ");
        int l = Integer.parseInt(spl[0]);
        int r = Integer.parseInt(spl[1]);
        br.append(2*query(l-1,r-1)+"\n");
    }
    System.out.println(br.toString());
    }

    public static void build(int idx, int l, int r) {
    if (l == r) {
        tree[idx] = 0;
    } else {
        int left = L(idx);
        int right = R(idx);
        build(left, l, (l+r)/2);
        build(right, (l+r)/2+1, r);
        int max = tree[left] + tree[right];
        //AND CROSSOVER:
        //left is from [l, (l+r)/2]
        //right is from [(l+r)/2 + 1, r]
        int leftL = getLeft(l, (l+r)/2) - tree[left];
        int leftR = getRight(l, (l+r)/2) - tree[left];
        int rightL = getLeft((l+r)/2 + 1, r) - tree[right];
        int rightR = getRight((l+r)/2+1, r) - tree[right];
        max += Math.min(Math.max(0,leftL), Math.max(rightR,0));
        tree[idx] = max;
        //System.out.println("L: " + l + " R: " + r + " VAL: " + max);
        //System.out.println("Checked [" + l + "," + ((l+r)/2) + "] and got: " + tree[left] + " WITH leftL: " + leftL);
        //System.out.println("Checked [" + ((l+r)/2+1) + "," + r + "] and got: " + tree[right] + " WITH rightR: " + rightR);
    }
    //System.out.println("L: " + l + " R: " + r + " VAL: " + tree[idx]);
    }

    public static int getLeft(int l, int r) {
    int res = left[r];
    if (l > 0) res -= left[l-1];
    return res;
    }

    public static int getRight(int l, int r) {
    int res = right[r];
    if (l > 0) res -= right[l-1];
    return res;
    }

    public static int L(int N) {
        return 2 * N + 1;
    }

    public static int R(int N) {
        return 2 * N + 2;
    }

    public static int query(int i, int j) {
    return query(0, 0, N-1, i, j);
    }

    public static int query(int idx, int l, int r, int i, int j) {
    if (i > r || j < l) return 0;
    if (l >= i && r <= j) return tree[idx];
        int res = 0;//todo combine
    int leftQ = query(L(idx), l, (l+r)/2, i, j);
    int rightQ = query(R(idx), (l+r)/2+1, r, i, j);
    //i <= r and j >= l
    int maxL = Math.max(i, l);
    int minR = Math.min(j, r);
    //[maxL, (l+r)/2] U [(l+r)/2+1, minR]
    int left = getLeft(maxL, (l+r)/2)-leftQ;
    int right = getRight((l+r)/2+1, minR)-rightQ;
    return leftQ+rightQ+Math.min(Math.max(0, left), Math.max(0, right));
    }
}
