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.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Collection;
import java.util.Locale;
import java.util.StringTokenizer;

public class C380 {

        public static void main(String[] args) throws IOException {
            new Thread(null, new Runnable() {
                public void run() {
                    try {
                        long prevTime = System.currentTimeMillis();
                        new C380().run();
                        System.err.println("Total time: " + (System.currentTimeMillis() - prevTime) + " ms");
                        System.err.println("Memory status: " + memoryStatus());
                    } catch (IOException e) {
                        e.printStackTrace();
                    }
                }
            }, "1", 1L << 27).start();
        }

    void run() throws IOException {
        in = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        Object o = solve();
        if (o != null)
            out.println(o);
        out.close();
        in.close();
    }

    private Object solve() throws IOException {
        String s = in.readLine();
        int n = s.length();
        Block[] bs = new Block[n];
        for(int i =0; i < n;i++)
            if(s.charAt(i)=='('){
                bs[i] = new Block(1,0,0);
            } else {
                bs[i] = new Block(0,1,0);
            }
        int q = ni();
        SegmentTree st = new SegmentTree(bs);
        for(int i =0; i < q;i++){
            int l = ni()-1;
            int r = ni();
            out.println(2 * st.get(l, r).complete);

        }

        return null;
    }

    public class SegmentTree {

        int n; // array size
        Block[] t;

        public SegmentTree(Block[] arr) {
            n = arr.length;
            t = new Block[2 * n];
            System.arraycopy(arr, 0, t, n, n);
            build();
        }

        void build() {  // build the tree
            for (int i = n - 1; i > 0; --i)
                t[i] = t[i<<1].combine(t[i<<1|1]);
        }

        Block get(int l, int r) { // sum on interval [l, r)
            Block res_left = new Block(0, 0, 0); // base
            Block res_right = new Block(0, 0, 0);

            for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
                if ((l & 1) != 0)
                    res_left = res_left.combine(t[l++]); // combine
                if ((r & 1) != 0)
                    res_right = t[--r].combine(res_right); // combine
            }
            return res_left.combine(res_right); // combine
        }
    }

    class Block {
        int open;
        int close;
        int complete;

        public Block(int open, int close, int complete) {
            this.open = open;
            this.close = close;
            this.complete = complete;
        }

        public Block combine(Block o) {

            int add = Math.min(open, o.close);
            int new_open = open + o.open - add;
            int new_close = close + o.close - add;

            int new_complete = complete + o.complete + add;

            return new Block(new_open, new_close, new_complete);
        }
    }

    BufferedReader in;
    PrintWriter out;
    StringTokenizer strTok = new StringTokenizer("");

    String nextToken() throws IOException {
        while (!strTok.hasMoreTokens())
            strTok = new StringTokenizer(in.readLine());
        return strTok.nextToken();
    }

    int ni() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nl() throws IOException {
        return Long.parseLong(nextToken());
    }

    double nd() throws IOException {
        return Double.parseDouble(nextToken());
    }

    int[] nia(int size) throws IOException {
        int[] ret = new int[size];
        for (int i = 0; i < size; i++)
            ret[i] = ni();
        return ret;
    }

    long[] nla(int size) throws IOException {
        long[] ret = new long[size];
        for (int i = 0; i < size; i++)
            ret[i] = nl();
        return ret;
    }

    double[] nda(int size) throws IOException {
        double[] ret = new double[size];
        for (int i = 0; i < size; i++)
            ret[i] = nd();
        return ret;
    }

    String nextLine() throws IOException {
        strTok = new StringTokenizer("");
        return in.readLine();
    }

    boolean EOF() throws IOException {
        while (!strTok.hasMoreTokens()) {
            String s = in.readLine();
            if (s == null)
                return true;
            strTok = new StringTokenizer(s);
        }
        return false;
    }

    void printRepeat(String s, int count) {
        for (int i = 0; i < count; i++)
            out.print(s);
    }

    void printArray(int[] array) {
        for (int i = 0; i < array.length; i++) {
            if (i > 0)
                out.print(' ');
            out.print(array[i]);
        }
        out.println();
    }

    void printArray(long[] array) {
        for (int i = 0; i < array.length; i++) {
            if (i > 0)
                out.print(' ');
            out.print(array[i]);
        }
        out.println();
    }

    void printArray(double[] array) {
        for (int i = 0; i < array.length; i++) {
            if (i > 0)
                out.print(' ');
            out.print(array[i]);
        }
        out.println();
    }

    void printArray(double[] array, String spec) {
        for (int i = 0; i < array.length; i++) {
            if (i > 0)
                out.print(' ');
            out.printf(Locale.US, spec, array[i]);
        }
        out.println();
    }

    void printArray(Object[] array) {
        boolean blank = false;
        for (Object x : array) {
            if (blank)
                out.print(' ');
            else
                blank = true;
            out.print(x);
        }
        out.println();
    }

    @SuppressWarnings("rawtypes")
    void printCollection(Collection collection) {
        boolean blank = false;
        for (Object x : collection) {
            if (blank)
                out.print(' ');
            else
                blank = true;
            out.print(x);
        }
        out.println();
    }

    static String memoryStatus() {
        return (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory() >> 20) + "/"
                + (Runtime.getRuntime().totalMemory() >> 20) + " MB";
    }

    public void pln() {
        out.println();
    }

    public void pln(int arg) {
        out.println(arg);
    }

    public void pln(long arg) {
        out.println(arg);
    }

    public void pln(double arg) {
        out.println(arg);
    }

    public void pln(String arg) {
        out.println(arg);
    }

    public void pln(boolean arg) {
        out.println(arg);
    }

    public void pln(char arg) {
        out.println(arg);
    }

    public void pln(float arg) {
        out.println(arg);
    }

    public void pln(Object arg) {
        out.println(arg);
    }

    public void p(int arg) {
        out.print(arg);
    }

    public void p(long arg) {
        out.print(arg);
    }

    public void p(double arg) {
        out.print(arg);
    }

    public void p(String arg) {
        out.print(arg);
    }

    public void p(boolean arg) {
        out.print(arg);
    }

    public void p(char arg) {
        out.print(arg);
    }

    public void p(float arg) {
        out.print(arg);
    }

    public void p(Object arg) {
        out.print(arg);
    }

}
