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.IOException;
import java.io.InputStream;

import static java.lang.Integer.min;

public final class SerejaAndBrackets {

    static int tree[] = new int[4000002];
    static int o[] = new int[4000002];
    static int c[] = new int[4000002];
    static char a[] = new char[1000000];

    public static void main(String[] args) throws IOException {
        FastReader br = FastReader.SYSTEM_READER;
        String s, temp[];
        int m, l, r, n;
        s = br.nextString();
        n = s.length();
        s.getChars(0, n, a, 0);
        buildTree(1, 0, n);
        m = br.nextInt();
        for (int i = 0; i < m; i++) {
            //temp = br.readLine().split("\\s");
            l = br.nextInt();
            r = br.nextInt();
            System.out.println(query(1, 0, n, l - 1, r)[0]*2);
        }

    }

    //return value description -> t[maximumBracket subsequence length, no. of open brackets in range, no. of closed brackets in range]
    //start end represents the range covered by the node id
    //l and r is the range of the query asked
    private static int[] query(int id, int start, int end, int l, int r) {
        if (start >= r || end <= l) {
            return new int[]{0, 0, 0};
        }
        if (start >= l && end <= r) {
            return new int[]{tree[id], o[id], c[id]};
        }
        int mid = (start + end) / 2;
        int leftChild = id << 1, rightChild = (id << 1) + 1;
        int left[] = query(leftChild, start, mid, l, r);
        int right[] = query(rightChild, mid, end, l, r);
        //min of no. of open brackets in left child and closed brackets in right child
        int tmp = min(left[1], right[2]);
        int o = left[1] + right[1] - tmp;
        int c = left[2] + right[2] - tmp;
        int t = left[0] + right[0] + tmp;
        return new int[]{t, o, c};
    }
    private static void buildTree(int id, int l, int r) {
        if (r - l < 2) {
            if (a[l] == '(') {
                o[id] = 1;
            } else {
                c[id] = 1;
            }
            return;
        }
        int mid = (l + r) / 2;
        int leftChild = id << 1, rightChild = (id << 1) + 1;
        buildTree(leftChild, l, mid);
        buildTree(rightChild, mid, r);
        int tmp = min(o[id << 1], c[(id << 1) + 1]);
        o[id] = o[leftChild] + o[rightChild] - tmp;
        c[id] = c[leftChild] + c[rightChild] - tmp;
        tree[id] = tree[leftChild] + tree[rightChild] + tmp;
    }

    static final class FastReader {
        public static final FastReader SYSTEM_READER = new FastReader(System.in);
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int pos, count;

        public FastReader(InputStream in) {
            this.in = in;
            pos = count = 0;
        }

        public int nextInt() {
            int c;
            while ((c = read()) < '0');
            int result = c - '0';
            while ((c = read() - '0') >= 0)
                result = 10 * result + c;
            return result;
        }
        public long nextLong() {
            int c;
            while ((c = read()) < '0');
            long result = c - '0';
            while ((c = read() - '0') >= 0)
                result = 10 * result + c;
            return result;
        }

        public String nextString() {
            StringBuilder s = new StringBuilder();
            int c;
            while ((c = read()) >= 33)
                s.append((char) c);
            return s.toString();
        }

        private void fillBuffer() {
            try {
                count = in.read(buffer, pos = 0, buffer.length);
            } catch (Exception e) {
            }
        }

        public int read() {
            if (pos == count)
                fillBuffer();
            return buffer[pos++];
        }
    }
}
