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.util.*;
    import java.io.*;
 
     public class CodeForces {
        
        
        public static void main(String[] args) throws IOException {
            Reader.init(System.in);
            PrintWriter writer = new PrintWriter(System.out);
            
            String s = Reader.next();
            STree sTree = new STree(s);
            sTree.build(1, s.length(), 1);
//            
//            for (int i = 1; i < 25; i++) {
//                writer.printf("%d\t%d\t%d\t%d\n", i, sTree.tree[i], sTree.open[i], sTree.close[i]);
//            }
            writer.flush();
            int q = Reader.nextInt();
            while(q != 0){
                q--;
                int l = Reader.nextInt();
                int r = Reader.nextInt();
                
                writer.println(sTree.query(1, s.length(), l, r, 1));
            }
            
            writer.close();
        }
    }

class NN {
    int[] open, close, tree;

    public NN(int n) {
        tree = new int[n*5];
        open = new int[n*5];
        close = new int[n*5];
    }
    
}
class STree{
    NN build, ans;
    char arr[];
    
    public STree(String s) {
        build = new NN(s.length());
        ans = new NN(s.length());
        arr = new char[s.length()+1];
        for (int i = 0; i < s.length(); i++) {
            arr[i+1] = s.charAt(i);
        }
    }
    
    
    void build(int l, int r, int node){
        if(l > r)
            return;
        
        if(l == r){
            build.tree[node] = 0;
            if(arr[r] == '(')
                build.open[node] = 1;
            else
                build.close[node] = 1;
            return;
        }
        
        build(l, (l+r)/2, node*2);
        build((l+r)/2+1, r, node*2+1);
        
        int min = Math.min(build.open[node*2], build.close[node*2+1]);
        
        build.tree[node] = build.tree[node*2] + build.tree[node*2+1] + (min * 2);
        build.open[node] = build.open[node*2] + build.open[node*2+1] - min;
        build.close[node] = build.close[node*2] + build.close[node*2+1] - min;
    }

    int query(int l, int r, int start, int end, int node){
        if(r < l)
            return 0;
        if(l > end || r < start){
            ans.tree[node] = ans.open[node] = ans.close[node] = 0;
            return 0;
        }
        
        if(l >= start && r <= end){
            ans.close[node] = build.close[node];
            ans.open[node] = build.open[node];
            return ans.tree[node] = build.tree[node];
        }
        
//        return Math.max(query(l, (l+r) / 2, start, end, node*2), query((l+r) / 2  + 1, r, start, end, node*2+1));
        
        
        query(l, (l+r)/2, start, end, node*2);
        query((l+r)/2+1, r, start, end, node*2+1);

        int min = Math.min(ans.open[node*2], ans.close[node*2+1]);
        
        ans.tree[node] = ans.tree[node*2] + ans.tree[node*2+1] + (min * 2);
        ans.open[node] = ans.open[node*2] + ans.open[node*2+1] - min;
        ans.close[node] = ans.close[node*2] + ans.close[node*2+1] - min;
        
        return ans.tree[node];
    }
}
    class  Edge implements Comparable<Edge>{
 
        int to;
        int from;
        int cost;
        
        Edge(int a, int b, int c){
            from = a;
            to = b;
            cost = c;
        }
 
        @Override
        public int compareTo(Edge t) {
            return t.cost - cost;
        }
    }
 
 
class Pair {
    int x, y;

    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
        
            
    public Pair clone(){
        return new Pair(x, y);
    }

    @Override
    public String toString() {
        return this.x + ", " + this.y;
    }

    @Override
    public boolean equals(Object obj) {
        Pair other = (Pair)obj;
        
        return this.x == other.x && this.y == other.y;
    }

    @Override
    public int hashCode() {
        return (x*y) % ((int)1e9 + 7);
    }

    
}
 
 
    class Reader {
 
        static BufferedReader reader;
        static StringTokenizer tokenizer;
 
        public static int pars(String x) {
            int num = 0;
            int i = 0;
            if (x.charAt(0) == '-') {
                i = 1;
            }
            for (; i < x.length(); i++) {
                num = num * 10 + (x.charAt(i) - '0');
            }
 
            if (x.charAt(0) == '-') {
                return -num;
            }
 
            return num;
        }
 
        static void init(InputStream input) {
            reader = new BufferedReader(
                    new InputStreamReader(input));
            tokenizer = new StringTokenizer("");
        }
 
        static void init(FileReader input) {
            reader = new BufferedReader(input);
            tokenizer = new StringTokenizer("");
        }
 
        static String next() throws IOException {
            while (!tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(
                        reader.readLine());
            }
            return tokenizer.nextToken();
        }
 
        static int nextInt() throws IOException {
            return pars(next());
        }
 
        static long nextLong() throws IOException {
            return Long.parseLong(next());
        }
 
        static double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
    }