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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.io.InputStream;

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

    static class CSerejaAndBrackets {
        public void solve(int testNumber, Scanner sc, PrintWriter pw) {
            char[] arr = sc.next().toCharArray();
            int N = 1;
            while (N < arr.length)
                N <<= 1;
            int[] in = new int[N + 1];
            for (int i = 1; i < arr.length + 1; i++)
                in[i] = arr[i - 1] == '(' ? 1 : 2;
            int q = sc.nextInt();
            CSerejaAndBrackets.SegmentTree sTree = new CSerejaAndBrackets.SegmentTree(in);
            while (q-- > 0) {
                pw.println(sTree.query(sc.nextInt(), sc.nextInt()) * 2);
            }
        }

        static class triple {
            int left;
            int right;
            int max;

            public triple(int left, int right, int max) {
                this.left = left;
                this.right = right;
                this.max = max;
            }

            public String toString() {
                return left + " " + right + " " + max;
            }

            public CSerejaAndBrackets.triple add(CSerejaAndBrackets.triple triple) {
                int min = Math.min(left, triple.right);
                return new CSerejaAndBrackets.triple(left + triple.left - min, right + triple.right - min, min + triple.max + max);
            }

        }

        static public class SegmentTree {
            int N;
            int[] array;
            CSerejaAndBrackets.triple[] sTree;

            SegmentTree(int[] in) {
                array = in;
                N = in.length - 1;
                sTree = new CSerejaAndBrackets.triple[N << 1];        //no. of nodes = 2*N - 1, we add one to cross out index zero
                build(1, 1, N);
            }

            void build(int node, int b, int e) {
                if (b == e)
                    sTree[node] = array[b] == 1 ? new CSerejaAndBrackets.triple(1, 0, 0) : array[b] == 2 ? new CSerejaAndBrackets.triple(0, 1, 0) : new CSerejaAndBrackets.triple(0, 0, 0);
                else {
                    int mid = b + e >> 1;
                    build(node << 1, b, mid);
                    build(node << 1 | 1, mid + 1, e);
                    sTree[node] = sTree[node << 1].add(sTree[node << 1 | 1]);
                }
            }

            int query(int i, int j) {
                return query(1, 1, N, i, j).max;
            }

            CSerejaAndBrackets.triple query(int node, int b, int e, int i, int j) {
                if (i > e || j < b)
                    return new CSerejaAndBrackets.triple(0, 0, 0);
                if (b >= i && e <= j)
                    return sTree[node];
                int mid = b + e >> 1;
                CSerejaAndBrackets.triple q1 = query(node << 1, b, mid, i, j);
                CSerejaAndBrackets.triple q2 = query(node << 1 | 1, mid + 1, e, i, j);
                return q1.add(q2);
            }

        }

    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(FileReader r) {
            br = new BufferedReader(r);
        }

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}

