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.*;

public class P380C {
    private static class HpReader {
        private BufferedReader in;

        public HpReader(String dir, String inFile, String outFile) {
            initAndRedirectInOut(dir, inFile, outFile);
        }

        private static int ivl(String val) {
            return Integer.parseInt(val);
        }

        private static long lvl(String val) {
            return Long.parseLong(val);
        }

        private void initAndRedirectInOut(String dir, String inFile, String outFile) {
            if (dir != null) {
                try {
                    String containingDirPath = dir.endsWith(File.separator) ? dir : dir + File.separator;
                    if (isDebug && inFile != null) System.setIn(new FileInputStream(new File(containingDirPath + inFile)));
                    if (isDebug && outFile != null) System.setOut(new PrintStream(new File(containingDirPath + outFile)));
                } catch (FileNotFoundException e) {
                    // Do nothing, stdin & stdout are not redirected
                }
            }
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
        }

        private String nextSingleStr() throws IOException {
            return in.readLine();
        }

        private String[] nextLineStr() throws IOException {
            return nextLineStr(0);
        }

        private String[] nextLineStr(int offset) throws IOException {
            String[] inp = nextSingleStr().split(" ");
            String[] rs = new String[offset + inp.length];
            System.arraycopy(inp, 0, rs, offset, inp.length);
            return rs;
        }

        private int nextSingleInt() throws IOException {
            return ivl(in.readLine());
        }

        private int[] nextLineInt() throws IOException {
            return nextLineInt(0);
        }

        private int[] nextLineInt(int offset) throws IOException {
            String[] inp = nextLineStr();
            int[] rs = new int[offset + inp.length];
            for (int i = 0; i < inp.length; i++) rs[offset + i] = ivl(inp[i]);
            return rs;
        }

        private long nextSingleLong() throws IOException {
            return lvl(in.readLine());
        }

        private long[] nextLineLong() throws IOException {
            return nextLineLong(0);
        }

        private long[] nextLineLong(int offset) throws IOException {
            String[] inp = nextLineStr();
            long[] rs = new long[offset + inp.length];
            for (int i = 0; i < inp.length; i++) rs[offset + i] = lvl(inp[i]);
            return rs;
        }

        private int[][] nextMatInt(int lineCount) throws IOException {
            return nextMatInt(lineCount, 0, 0);
        }

        private int[][] nextMatInt(int lineCount, int rowOffset, int colOffset) throws IOException {
            int[][] rs = new int[rowOffset + lineCount][];
            for (int i = rowOffset; i < rs.length; i++) rs[i] = nextLineInt(colOffset);
            return rs;
        }
    }

    private static class HpHelper {
        private static final String LOCAL_DEBUG_FLAG = "COM_PROG_DEBUG";

        private static boolean isDebug() {
            try {
                return Boolean.parseBoolean(System.getenv(HpHelper.LOCAL_DEBUG_FLAG));
            } catch (Exception e) {
                return false;
            }
        }

        private static String createDelimiter(String delimiter) {
            return delimiter == null ? " " : delimiter;
        }

        private static void println(int[] data, String delimiter) {
            delimiter = createDelimiter(delimiter);
            for (int t : data) out.print(t + delimiter);
            out.println();
        }

        private static void println(long[] data, String delimiter) {
            delimiter = createDelimiter(delimiter);
            for (long t : data) out.print(t + delimiter);
            out.println();
        }

        private static <T> void println(T[] data, String delimiter) {
            delimiter = createDelimiter(delimiter);
            for (T t : data) {
                if (t instanceof int[]) {
                    println((int[]) t, delimiter);
                } else if (t instanceof long[]) {
                    println((long[]) t, delimiter);
                } else if (t instanceof Object[]) {
                    println((Object[]) t, delimiter);
                } else {
                    out.print(t + delimiter);
                }
            }
            out.println();
        }
    }

    private static boolean isDebug = HpHelper.isDebug();
    private static HpReader in = new HpReader("/Users/apple/Work/WorkSpaces/CompetitiveProg/", "in.txt", null);
    private static PrintWriter out;

    private static int mergePair(int t1, int o1, int c1, int t2, int o2, int c2) {
        return t1 + t2 + 2 * Math.min(o1, c2);
    }

    private static int mergeOpen(int t1, int o1, int c1, int t2, int o2, int c2) {
        return o1 + o2 - Math.min(o1, c2);
    }

    private static int mergeClose(int t1, int o1, int c1, int t2, int o2, int c2) {
        return c1 + c2 - Math.min(o1, c2);
    }

    private static int[] merge(int t1, int o1, int c1, int t2, int o2, int c2) {
        int rst = mergePair(t1, o1, c1, t2, o2, c2);
        int rso = mergeOpen(t1, o1, c1, t2, o2, c2);
        int rsc = mergeClose(t1, o1, c1, t2, o2, c2);

        return new int[]{rst, rso, rsc};
    }

    public static void main(String[] args) throws IOException {
        String inp = in.nextSingleStr();
        int m = in.nextSingleInt();

        int[] t = new int[inp.length() * 2], o = new int[inp.length() * 2], c = new int[inp.length() * 2];
        for (int i = 0; i < inp.length(); i++) {
            int index = inp.length() + i;
            char ch = inp.charAt(i);

            o[index] = ch == '(' ? 1 : 0;
            c[index] = ch == ')' ? 1 : 0;
            t[index] = 0;
        }
        for (int i = inp.length() - 1; i >= 1; i--) {
            int idx1 = i << 1, idx2 = i << 1 | 1;
            int[] rs = merge(t[idx1], o[idx1], c[idx1], t[idx2], o[idx2], c[idx2]);
            t[i] = rs[0];
            o[i] = rs[1];
            c[i] = rs[2];
        }

        for (int qr = 1; qr <= m; qr++) {
            int[] inq = in.nextLineInt();
            out.println(query(o, c, t, inq[0] - 1, inq[1] - 1, inp.length()));
        }

        out.flush();
    }

    private static int query(int[] o, int[] c, int[] t, int l, int r, int n) {
        int[] rsl = new int[3], rsr = new int[3];
        for (l += n, r += n; l <= r; l /= 2, r /= 2) {
            if (l % 2 == 1) {
                rsl = merge(rsl[0], rsl[1], rsl[2], t[l], o[l], c[l]);
                l += 1;
            }
            if (r % 2 == 0) {
                rsr = merge(t[r], o[r], c[r], rsr[0], rsr[1], rsr[2]);
                r -= 1;
            }

            if (l == r) break;
        }

        int[] rs = merge(rsl[0], rsl[1], rsl[2], rsr[0], rsr[1], rsr[2]);

        return rs[0];
    }
}
