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.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Random;
import java.util.TreeSet;

public class E {

    
    static void compute(String s, int[] l, int[] r, int[] out) {
        int n=s.length(), m=l.length;
        int[] 
                st=new int[n], 
                cnt=new int[n], 
                l2r=new int[n],
                l2qcnt=new int[n];
        //prepare queries
        for (int i=0; i<m; i++) {
            l2qcnt[l[i]]++;
        }
        
        int[][] l2q=new int[n][];
        for (int i=0; i<n; i++) {
            l2q[i]=new int[l2qcnt[i]];
        }
        for (int i=0; i<m; i++) {
            int j=l[i];
            l2q[j][--l2qcnt[j]]=i;
        }
        //end of prepare queries
        
        Arrays.fill(l2r, -1);
        int ssize=0;
        for (int i=0; i<n; i++) {
            if(s.charAt(i)=='(') {
                st[ssize++]=i;
            } else {
                if(ssize>0) {
                    l2r[st[--ssize]]=i;
                    cnt[i]+=2;
                }
            }
        }
        
        for (int i=1; i<n; i++) {
            cnt[i]+=cnt[i-1];
        }
        
        TreeSet<Integer> is=new TreeSet<Integer>();
        for (int i=0; i<n; i++) {
            for (int j=0; j<l2q[i].length; j++) {
                int q=l2q[i][j];
                out[q]=cnt[r[q]]-(l[q]>0? cnt[l[q]-1]: 0)-(is.headSet(r[q], true).size()<<1);
            }
            is.remove(i);
            if(l2r[i]>=0) {
                is.add(l2r[i]);
            }
        }
        
    }
    
    
    
    
    
    
    
    
    
    
    
    static StringBuilder sb=new StringBuilder();
    static void run_stream(InputStream ins) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String s=br.readLine();
        
        int n=Integer.parseInt(br.readLine());
        int[] l=new int[n], r=new int[n];
        for (int i=0; i<n; i++) {
            String line=br.readLine();
            int space=line.indexOf(' ');
            l[i]=Integer.parseInt(line.substring(0, space))-1;
            r[i]=Integer.parseInt(line.substring(space+1, line.length()))-1;
        }
        
        int[] out=new int[n];
        compute(s, l, r, out);
        
        
        sb.setLength(0);
        sb.append(out[0]);
        for (int i=1; i<out.length; i++) {
            sb.append("\n"+out[i]);
        }
        
        System.out.println(sb.toString());

        
        
        
        
//        int[] blout=new int[n];
//        for (int i=0; i<n; i++) {
//            blout[i]=baseline(s, l[i], r[i]);
//        }
//        sb.setLength(0);
//        sb.append(blout[0]);
//        for (int i=1; i<blout.length; i++) {
//            sb.append(" "+blout[i]);
//        }
//        System.out.println(sb.toString());
    }
    
    public static void main(String[] args) throws IOException {
        run_stream(System.in);
        
        //run_random();
    }
    
    
    
    static Random rnd=new Random();
    static void run_random() {
        sb.setLength(0);
        int n=2000;
        for (int i=0; i<n; i++) {
            sb.append(rnd.nextBoolean()? '(': ')');
        }
        String s=sb.toString();
        int m=20000;
        int[] l=new int[m], r=new int[m];
        for (int i=0; i<m; i++) {
            l[i]=rnd.nextInt(n);
            r[i]=rnd.nextInt(n);
            if(l[i]>r[i]) {
                int j=l[i]; l[i]=r[i]; r[i]=j;
            }
        }
        
        int[] out=new int[m];
        compute(s, l, r, out);
        
        int[] blout=new int[m];
        for (int i=0; i<m; i++) {
            blout[i]=baseline(s, l[i], r[i]);
        }
        
        if(!Arrays.equals(out, blout)) {
            System.out.println("found diffs: ");
            System.out.println(Arrays.toString(out));
            System.out.println(Arrays.toString(blout));
            System.out.println();
            System.out.println(s);
            System.out.println(Arrays.toString(l));
            System.out.println(Arrays.toString(r));
            
            int cnt=0;
            for (int i=0; i<m; i++) {
                if(out[i]!=blout[i]) {
                    cnt++;
                }
            }
            
            System.out.println();
            System.out.println(s);
            System.out.println(cnt);
            for (int i=0; i<m; i++) {
                if(out[i]!=blout[i]) {
                    System.out.println((l[i]+1)+" "+(r[i]+1));
                }
            }

            System.out.println();
            System.out.println(s);
            System.out.println(m);
            for (int i=0; i<m; i++) {
                System.out.println((l[i]+1)+" "+(r[i]+1));
            }
            
        } else {
            System.out.println("all good");
        }
    }
    
    static int baseline(String s, int l, int r) {
        int ocnt=0, ret=0;
        for (int i=l; i<=r; i++) {
            if(s.charAt(i)=='(') {
                ocnt++;
            } else if(ocnt>0) {
                ocnt--;
                ret+=2;
            }
        }
        return ret;
    }

}
