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

public class C {

    BufferedReader br;
    PrintWriter out;
    StringTokenizer st;
    boolean eof;

    void add(int[] f, int pos) {
        for (int i = pos; i < f.length; i |= i + 1) {
            f[i]++;
        }
    }

    int get(int[] f, int pos) {
        int ret = 0;
        for (int i = pos; i >= 0; i = (i & (i + 1)) - 1)
            ret += f[i];
        return ret;
    }

    void solve() throws IOException {
        char[] s = nextToken().toCharArray();
        int[] op = new int[s.length];
        int szOp = 0;

        int[] corrOpen = new int[s.length];
        int[] corrClose = new int[s.length];
        int szCorr = 0;

        for (int i = 0; i < s.length; i++) {
            if (s[i] == '(') {
                op[szOp++] = i;
            } else {
                if (szOp == 0)
                    continue;
                corrOpen[szCorr] = op[--szOp];
                corrClose[szCorr] = i;
                szCorr++;
            }
        }

        int q = nextInt();
        Query[] qq = new Query[q];
        for (int i = 0; i < q; i++) {
            qq[i] = new Query(nextInt() - 1, nextInt() - 1, i);
        }

        Arrays.sort(qq);

        int[] ans = new int[q];
        int[] fen = new int[s.length];

        for (int i = 0, j = 0; i < q; i++) {
            Query cur = qq[i];
            while (j < szCorr && corrClose[j] <= cur.r) {
                add(fen, corrOpen[j++]);
            }
            ans[cur.ind] = get(fen, cur.r) - get(fen, cur.l - 1);
        }
        
        for (int i = 0; i < q; i++) {
            out.println(ans[i] << 1);
        }

    }

    static class Query implements Comparable<Query> {
        int l, r, ind;

        public Query(int l, int r, int ind) {
            this.l = l;
            this.r = r;
            this.ind = ind;
        }

        @Override
        public int compareTo(Query o) {
            return Integer.compare(r, o.r);
        }

    }

    C() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        solve();
        out.close();
    }

    public static void main(String[] args) throws IOException {
        new C();
    }

    String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                eof = true;
                return null;
            }
        }
        return st.nextToken();
    }

    String nextString() {
        try {
            return br.readLine();
        } catch (IOException e) {
            eof = true;
            return null;
        }
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
}
