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


public class SerejaandBrackets {
    public static class Node{
        int open,close,full;
        public Node(int a,int b,int c){
            open = a;
            close = b;
            full = c;
        }
    }
    static char[] input;
    static Node[] seg;
    static void build(int l ,int r,int v){
        if(l==r){
            seg[v] =input[l]=='('?  new Node(1, 0, 0):new Node(0, 1, 0);
            return ;
        }
        else{
            int mid = (l+r)>>1;
            build(l, mid, 2*v);
            build(mid+1, r, 2*v+1);
            int newFull = Math.min(seg[2*v].open, seg[2*v+1].close);
            int a = seg[2*v].open +seg[2*v+1].open-newFull ;
            int b = seg[2*v].close+seg[2*v+1].close-newFull;
            int c = seg[2*v].full+seg[2*v+1].full+newFull;      
            seg[v] = new Node(a, b, c);
        }
    }
    static Node query(int l,int r,int currL,int currR,int v){
        if(currL>r||currR<l){
            return new Node(0, 0, 0);
        }
        if(currL>=l&&currR<=r){
            return seg[v];
        }
        else{
            int mid = (currL+currR)>>1;
            Node lc = query(l, r, currL, mid, 2*v);
            Node rc = query(l, r, mid+1, currR, 2*v+1);
            int newFull = Math.min(lc.open, rc.close);
            int a = lc.open +rc.open-newFull ;
            int b = lc.close+rc.close-newFull;
            int c = lc.full+rc.full+newFull;
            return new Node(a, b, c);
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        StringTokenizer st;
        input = in.readLine().trim().toCharArray();
        int n = input.length;
        seg = new Node[4*n];
        build(0, n-1, 1);
        int q = Integer.parseInt(in.readLine().trim());
        while(q-->0){
            st = new StringTokenizer(in.readLine());
            int l = Integer.parseInt(st.nextToken())-1;
            int r = Integer.parseInt(st.nextToken())-1;
            Node node = query(l, r, 0, n-1, 1);
            out.println(2*node.full);
        }
        in.close();
        out.close();
    }

}
