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.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

/**
 * User: dmitryt
 * Date: 04/07/2015
 */
public class CF380C1 {

    private static void solve(String s, int m, int[] ls, int[] rs) {
        String[] res = new String[m];
        char[] b = s.toCharArray();
        int[] h = new int[b.length + 1];

        SegmentTreeMin st = new SegmentTreeMin(b.length + 1);

        int height = 0;
        st.add(0, 0);
        for (int i = 0; i < b.length; i++) {
            if (b[i] == '(') {
                height++;
                h[i+1] = height;
                st.add(i+1, height);
            } else {
                height--;
                h[i+1] = height;
                st.add(i+1, height);
            }
        }

        for (int k = 0; k < m; k++) {
            int l = ls[k];
            int r = rs[k];

            int min = st.min(l-1, r);

            int removeR = h[l-1] - min;
            int removeL = h[r] - min;
            res[k] = String.valueOf(r - l + 1 - removeL - removeR);
        }

        System.out.println(String.join("\n", res));
    }

    private static int nextInt(StreamTokenizer st) throws Exception {
        int token = st.nextToken();
        while (token != StreamTokenizer.TT_NUMBER) token = st.nextToken();
        return (int)st.nval;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        String s = in.readLine();
        StreamTokenizer st = new StreamTokenizer(in);

        int m = nextInt(st);
        int[] l = new int[m];
        int[] r = new int[m];
        for (int i = 0; i < m; i++) {
            l[i] = nextInt(st);
            r[i] = nextInt(st);
        }
        solve(s, m, l, r);
    }


    public static class SegmentTreeMin {
        private int[] t;

        public SegmentTreeMin(int n) {
            t = new int[n + n];
        }

        public int get(int i) {
            return t[i + t.length / 2];
        }

        public void add(int i, int value) {
            i += t.length / 2;
            t[i] += value;
            for (; i > 1; i >>= 1)
                t[i >> 1] = Math.min(t[i], t[i ^ 1]);
        }

        public int min(int a, int b) {
            int res = Integer.MAX_VALUE;
            for (a += t.length / 2, b += t.length / 2; a <= b; a = (a + 1) >> 1, b = (b - 1) >> 1) {
                if ((a & 1) != 0)
                    res = Math.min(res, t[a]);
                if ((b & 1) == 0)
                    res = Math.min(res, t[b]);
            }
            return res;
        }
    }

}