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 «()(())(())».
/*
 ID: govind.3, GhpS, govindpatel
 LANG: JAVA
 TASK: Main 
 */

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {

    /**
     * Min segment Tree takes the minimum number at the root
     */
    class MinSegmentTree {

        /**
         * root: Tree root, balance: input array, rl,rr:
         * rl=0,rr=inputArray.length-1 minTree:segment Tree
         */
        private void initMinTree(int root, int rl, int rr, int[] balance, int[] minTree) {
            if (rl == rr) {
                minTree[root] = balance[rl];
                return;
            }
            int rm = (rl + rr) / 2;
            initMinTree(root * 2 + 1, rl, rm, balance, minTree);
            initMinTree(root * 2 + 2, rm + 1, rr, balance, minTree);
            minTree[root] = Math.min(minTree[root * 2 + 1], minTree[root * 2 + 2]);
        }

        /**
         * minTree:segment tree root:0 rl:0,rr:inputarray.length-1
         * l=queryleft-1(If 1 based index),r = queryright(1-based)
         */
        private int getMin(int[] minTree, int root, int rl, int rr, int l, int r) {
            //l = query left-1, r = query right
            if (l > r) {
                return Integer.MAX_VALUE;
            }
            if (l == rl && r == rr) {
                return minTree[root];
            }
            int rm = (rl + rr) / 2;
            return Math.min(getMin(minTree, root * 2 + 1, rl, rm, l, Math.min(r, rm)),
                    getMin(minTree, root * 2 + 2, rm + 1, rr, Math.max(rm + 1, l), r));
        }
    }
    //dsu next operation
    int[] next;

    private int next(int i) {
        if (next[i] == i) {
            return i;
        }
        return next[i] = next(next[i]);
    }

    //segment tree...
    private void set(int[] t, int ind, int val) {
        ind += (t.length / 2);
        t[ind] = val;
        int curr = 0;
        while (ind > 1) {
            ind >>= 1;
            if (curr == 0) {
                t[ind] = t[ind * 2] | t[ind * 2 + 1];
            } else {
                t[ind] = t[ind * 2] ^ t[2 * ind + 1];
            }
            curr ^= 1;
        }
    }

    //Binary Index tree
    class FenwickTree {

        int[] ft;
        int N;

        FenwickTree(int n) {
            this.N = n;
            ft = new int[N];
        }

        private int lowbit(int x) {
            return x & (-x);
        }

        void update(int pos, int val) {
            while (pos < N) {
                ft[pos] += val;
                pos |= pos + 1;//0-index
            }
        }

        int sum(int pos) {
            int sum = 0;
            while (pos >= 0) {
                sum += ft[pos];
                pos = (pos & (pos + 1)) - 1;
            }
            return sum;
        }

        int rangeSum(int left, int right) {
            return sum(right) - sum(left - 1);
        }
    }

    /**
     * BINARY SEARCH IN FENWICK TREE: l=1, r=N(length), at=sumRequired,
     * letter=TreeIndex(if there are many ft), ft=arrays of FT
     */
    private int binarySearch(int l, int r, int at, int letter, FenwickTree[] ft) {
        while (r - l > 0) {
            int mid = (l + r) / 2;
            int sum = ft[letter].sum(mid);
            if (sum < at) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }

    private int[] compress(int[] a) {
        int[] b = new int[a.length];
        for (int i = 0; i < a.length; i++) {
            b[i] = a[i];
        }
        Arrays.sort(b);
        int m = 0;
        for (int i = 0; i < b.length;) {
            int j = i;
            while (j < b.length && b[j] == b[i]) {
                j++;
            }
            b[m++] = b[i];
            i = j;
        }
        for (int i = 0; i < a.length; i++) {
            a[i] = Arrays.binarySearch(b, 0, m, a[i]);
        }
        return a;
    }

    class Query implements Comparable<Query> {

        int left, right, index;

        Query(int l, int r, int i) {
            left = l;
            right = r;
            index = i;
        }

        public int compareTo(Query other) {
            return right - other.right;
        }
    }

    private void solve() throws IOException {
        char[] stringChar = nextToken().toCharArray();
        int N = stringChar.length;
        int[] stack = new int[N];
        int stSize = 0;
        FenwickTree ft = new FenwickTree(N);
        int M = nextInt();
        Query[] query = new Query[M];
        int[] ans = new int[M];
        StringBuilder sb = new StringBuilder("");
        for (int i = 0; i < M; i++) {
            query[i] = new Query(nextInt() - 1, nextInt() - 1, i);
        }
        Arrays.sort(query);
        int l = 0;
        for (int i = 0; i < N; i++) {
            if (stringChar[i] == '(') {
                stack[stSize++] = i;
            } else {
                if (stSize > 0) {
                    stSize--;
                    ft.update(stack[stSize], 1);
                }
            }
            while (l < M && query[l].right == i) {
                ans[query[l].index] = ft.rangeSum(query[l].left, i);
                l++;
            }
        }
        for (int i = 0; i < M; i++) {
            sb.append(ans[i] * 2);
            sb.append("\n");
        }
        out.print(sb);
    }

    boolean isSorted(ArrayList<Integer> al) {
        int size = al.size();
        for (int i = 1; i < size - 2; i++) {
            if (al.get(i) > al.get(i + 1)) {
                return false;
            }
        }
        return true;
    }

    /**
     * SHUFFLE: shuffle the array 'a' of size 'N'
     */
    private void shuffle(int[] a, int N) {
        for (int i = 0; i < N; i++) {
            int r = i + (int) ((N - i) * Math.random());
            int t = a[i];
            a[i] = a[r];
            a[r] = t;
        }
    }

    /**
     * TEMPLATE-STUFF: main method, run method - ( fileIO and stdIO ) and
     * various methods for input like nextInt, nextLong, nextToken and
     * nextDouble with some declarations.
     */
    /**
     * For solution to the problem ... see the solve method
     */
    public static void main(String[] args) {
        new Main().run();
    }

    public void run() {
        try {
            in = new BufferedReader(new FileReader("D-large.in"));
            out = new PrintWriter(new BufferedWriter(new FileWriter("Main.out")));
            tok = null;
            solve();
            in.close();
            out.close();
            System.exit(0);
        } catch (IOException e) {//(FileNotFoundException e) {
            try {
                in = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(new OutputStreamWriter(System.out));
                tok = null;
                solve();
                in.close();
                out.close();
                System.exit(0);
            } catch (IOException ex) {
                System.out.println(ex.getMessage());
                System.exit(0);
            }
        }
    }

    private String nextToken() throws IOException {
        while (tok == null || !tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine());
        }
        return tok.nextToken();
    }

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

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

    private double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
    BufferedReader in;
    StringTokenizer tok;
    PrintWriter out;
}
