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.Arrays;
import java.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Jenish
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        ScanReader in = new ScanReader(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, ScanReader in, PrintWriter out) {
            char arr[] = in.scanString().toCharArray();
            SegmentTree s = new SegmentTree(arr.length, arr);
            int m = in.scanInt();
            while (m-- > 0) {
                int l = in.scanInt() - 1;
                int r = in.scanInt() - 1;

                out.println(s.getMax(l, r) * 2);
            }

        }

        public class SegmentTree {
            int n;
            char[] arr;
            int[] treedone;
            int[] treeopen;
            int[] treeclose;

            public SegmentTree(int n, char[] arr) {
                this.n = n;
                this.arr = Arrays.copyOf(arr, n);
                this.treedone = new int[(4 * n) + 5];
                this.treeopen = new int[(4 * n) + 5];
                this.treeclose = new int[(4 * n) + 5];
                build(1, 0, n - 1);
            }

            private void build(int node, int start, int end) {
                if (start == end) {
                    if (arr[start] == '(') treeopen[node]++;
                    else treeclose[node]++;
                } else {
                    int mid = (start + end) / 2;
                    build((node * 2), start, mid);
                    build((node * 2) + 1, mid + 1, end);
                    int min = Math.min(treeopen[node * 2], treeclose[(node * 2) + 1]);
                    treedone[node] = treedone[node * 2] + treedone[(node * 2) + 1] + min;
                    treeopen[node] = treeopen[node * 2] + treeopen[(node * 2) + 1] - min;
                    treeclose[node] = treeclose[node * 2] + treeclose[(node * 2) + 1] - min;
                }
            }

            public int getMax(int l, int r) {
                return queryRange(1, 0, n - 1, l, r)[0];
            }

            private int[] queryRange(int node, int start, int end, int l, int r) {
                if (start > end || start > r || end < l) return new int[]{0, 0, 0};
                if (start >= l && end <= r) return new int[]{treedone[node], treeopen[node], treeclose[node]};
                int mid = (start + end) / 2;
                int[] p1 = queryRange(node * 2, start, mid, l, r);
                int[] p2 = queryRange((node * 2) + 1, mid + 1, end, l, r);
                int min = Math.min(p1[1], p2[2]);
                return new int[]{p1[0] + p2[0] + min, p1[1] + p2[1] - min, p1[2] + p2[2] - min};
            }

        }

    }

    static class ScanReader {
        private byte[] buf = new byte[4 * 1024];
        private int INDEX;
        private BufferedInputStream in;
        private int TOTAL;

        public ScanReader(InputStream inputStream) {
            in = new BufferedInputStream(inputStream);
        }

        private int scan() {
            if (INDEX >= TOTAL) {
                INDEX = 0;
                try {
                    TOTAL = in.read(buf);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                if (TOTAL <= 0) return -1;
            }
            return buf[INDEX++];
        }

        public int scanInt() {
            int I = 0;
            int n = scan();
            while (isWhiteSpace(n)) n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    I *= 10;
                    I += n - '0';
                    n = scan();
                }
            }
            return neg * I;
        }

        public String scanString() {
            int c = scan();
            while (isWhiteSpace(c)) c = scan();
            StringBuilder RESULT = new StringBuilder();
            do {
                RESULT.appendCodePoint(c);
                c = scan();
            } while (!isWhiteSpace(c));
            return RESULT.toString();
        }

        private boolean isWhiteSpace(int n) {
            if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
            else return false;
        }

    }
}

