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.*;
import java.util.*;
import java.math.*;

public class Main {
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer tokenizer=null;

    public static void main(String[] args) throws IOException {
        new Main().execute();
    }

    void debug(Object...os) {
        System.out.println(Arrays.deepToString(os));
    }

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

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

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

    String ns() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens())
            tokenizer = new StringTokenizer(br.readLine());
        return tokenizer.nextToken();
    }

    String nline() throws IOException {
        tokenizer=null;
        return br.readLine();
    }


    //Main Code starts Here
    int totalCases, testnum;
    String S;
    Node st[];
    int stLen;

    void execute() throws IOException {
        totalCases = 1;
        preprocess();
        for(testnum = 1; testnum <= totalCases; testnum++) {
            if(!input())
                break;
            solve();
        }
    }

    void preprocess() throws IOException {

    }

    void solve() throws IOException {
        for (int i = 0; i <= stLen/2; i++) {
            Node n = new Node();            
            if (i < S.length() && S.charAt(i) == '(') {
                n.a = 0;
                n.b = 1;
                n.c = 0;
            }
            else if (i < S.length() && S.charAt(i) == ')') {
                n.a = 0;
                n.b = 0;
                n.c = 1;
            }
            else {
                n.a = 0;
                n.b = 0;
                n.c = 0;                
            }
            st[stLen/2 + i] = n;
        }

        for (int i = stLen/2 - 1; i >= 0; i--) {
            Node ln = st[i*2 + 1];
            Node rn = st[i*2 + 2];
            Node n = getNode(ln, rn);           
            st[i] = n;
        }

        int queries = ni();

        for (int i = 0; i < stLen; i++) {
            //debug(st[i].a, st[i].b, st[i].c);
        }

        for (int i = 0; i < queries; i++) {
            int start = ni();
            int end = ni();
            Node x = find(0,0,stLen/2,start-1,end-1);
            System.out.println(x.a * 2);
        }
    }

    Node find(int in, int l, int r, int start, int end) {
        //debug(in, l, r, start, end);
        if (start <= l && end >= r) {
            //debug(true);
            return st[in];
        }
        else if(end < l || start > r) {
            Node n = new Node();
            return n;
        }
        else {
            Node le = find(in * 2 + 1, l, (r+l)/2, start, end);
            Node ri = find(in * 2 + 2, (r+l)/2 + 1, r, start, end);

            Node x = getNode(le, ri);
            return x;
        }
    }

    Node getNode(Node ln, Node rn) {
        Node n = new Node();
        int t = Math.min(ln.b, rn.c);

        n.a = ln.a + rn.a + t;
        n.b = ln.b + rn.b - t;
        n.c = ln.c + rn.c - t;
        return n;
    }

    boolean input() throws IOException {
        S = ns();
        int len = S.length();
        int count = 0;
        int pow2 = 1;
        while(pow2<len) {
            count++;
            pow2 = pow2*2;
        }
        stLen = ((1<<(count+1)) - 1);
        //debug(stLen);
        st = new Node[stLen];
        return true;
    }

    class Node {
        int a;
        int b;
        int c;
    }
}