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.Arrays;
import java.util.StringTokenizer;

public class SerejaAndBrackets {

    boolean dedbug = false;
    static MyScanner sc;
    static PrintWriter out;


    public SerejaAndBrackets(){
        sc = new MyScanner();
        out = new PrintWriter(System.out);
    }

    public static void main(String[] args) {

        SerejaAndBrackets brackets = new SerejaAndBrackets();

        Tuple[] tuples;
        String input = sc.next();
        int q = sc.nextInt();

        tuples = new Tuple[q];
        for (int i = 0; i < q; i++) {
            tuples[i] = new Tuple(sc.nextInt(), sc.nextInt());
        }

        brackets.solve(input, tuples);

        out.close();
    }

    void solve(String input, Tuple[] tuples){
        SegmentTree tree = new SegmentTree(input);
        tree.buildTree(1, 0, input.length()-1);

        if(dedbug){
            System.out.println("Index");
            for (int i = 1; i < tree.triple.length; i++) {
                System.out.printf("%3d", i);
            }
            System.out.println();

            System.out.println("Result");
            for (int i = 1; i < tree.triple.length; i++) {
                System.out.printf("%3d", tree.triple[i].result);
            }
            System.out.println();

            System.out.println("Open");
            for (int i = 1; i < tree.triple.length; i++) {
                System.out.printf("%3d", tree.triple[i].open);
            }
            System.out.println();

            System.out.println("Closed");
            for (int i = 1; i < tree.triple.length; i++) {
                System.out.printf("%3d", tree.triple[i].closed);
            }
            System.out.println();
        }

        for(Tuple tuple : tuples){
            Triple triple = tree.query(tuple.l - 1, tuple.r - 1);
            out.println(triple.result);
        }
    }

    static class SegmentTree {
        Triple[] triple;
        String input;
        int size;

        public SegmentTree(String str){
            input = str;
            int n = str.length();
            size = getSegmentTreeSize(n);
            triple = new Triple[size];
            Arrays.fill(triple, new Triple(0, 0, 0));
        }

        int getSegmentTreeSize(int n) {
            int size = 1;
            for (; size < n; size *= 2);
            return 2 * size;
        }

        void buildTree(int node, int start, int end){
            if(start == end){
                int result = 0, open = 0, closed = 0;
                if(input.charAt(start) == '(')
                    open = 1;
                else
                    closed= 1;
                triple[node] = new Triple(result, open, closed);
                return;
            }

            int leftChild = 2  * node;
            int rightChild = 2 * node + 1;
            int mid = start + (end - start) / 2;
            buildTree(leftChild, start, mid);
            buildTree(rightChild, mid + 1, end);

            int matching = Math.min(triple[leftChild].open, triple[rightChild].closed);

            int result = triple[leftChild].result + triple[rightChild].result + 2 * matching;
            int open = triple[leftChild].open + triple[rightChild].open - matching;
            int closed = triple[leftChild].closed + triple[rightChild].closed - matching;
            triple[node] = new Triple(result, open, closed);
        }

        Triple query(int node, int start, int end, int l, int r){

            if(start > end || end < l || start > r)
                return new Triple(0, 0, 0);

            if(l <= start && end <= r)
                return triple[node];

            int mid = start + (end - start) / 2;
            Triple q1 = query(2 * node, start, mid, l, r);
            Triple q2 = query(2  * node + 1, mid + 1, end, l, r);

            int matching = Math.min(q1.open, q2.closed);
            int result = q1.result + q2.result + 2 * matching;
            int open = q1.open + q2.open - matching;
            int closed = q1.closed + q2.closed - matching;
            return new Triple(result, open, closed);
        }

        Triple query(int l, int r){
            return query(1, 0, input.length() - 1, l, r);
        }

    }

    static class Tuple {
        int l, r;

        public Tuple(int l, int r){
            this.l = l;
            this.r = r;
        }
    }

    static class Triple {
        int open, closed, result;
        public Triple(int result, int open, int closed){
            this.result = result;
            this.open = open;
            this.closed = closed;
        }
    }

    static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine(){
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}
