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 Main implements Runnable {
	class Data{
            int l, r;
            Data(int l, int r){
                this.l = l; this.r = r;
            }
        }	
        
        class Query{
            int id, l, r;
            Query(int id, int l, int r){
                this.id = id; this.l = l; this.r = r;
            }
        }
        
        int[] fn;
        
        void add(int at, int value){
            for( ; at < fn.length ; at = at | (at + 1)) fn[at] += value;
        }
        
        int get(int at){
            int ret = 0;
            for( ; at >= 0; at = (at & (at + 1)) - 1) ret += fn[at];
            return ret;
        }
        
	public void solve() throws IOException {
            ArrayList<Data> al = new ArrayList<>();
            
            char[] c = nextToken().toCharArray();
            LinkedList<Integer> ll = new LinkedList<>();
            
            for(int i = 0; i < c.length; i++){
                if(c[i] == ')'){
                    if(ll.isEmpty()) continue;
                    al.add(new Data(ll.pollLast(), i));
                }
                else{
                    ll.add(i);
                }
            }
        
           
            int Q = nextInt();
            Query[] qry = new Query[Q];
            for(int i = 0; i < Q; i++){
                qry[i]  = new Query(i, nextInt()-1, nextInt()-1);
            }
            
            Arrays.sort(qry, new Comparator<Query>(){
                public int compare(Query a, Query b){
                    return a.r - b.r;
                }
            });
            
            fn = new int[c.length + 10];
            int[] result = new int[Q];
            
            int index = 0;
            for(int i = 0; i < Q; i++){
                Query curQ = qry[i];
                while(index < al.size() && al.get(index).r <= curQ.r){
                    add(al.get(index).l, 1);
                    index++;
                }
                
                int answer = get(curQ.r) -  get(curQ.l - 1);
                
                result[curQ.id] = answer * 2;
            }
            
            for(int i = 0; i < Q; i++){
                out.println(result[i]);
            }
	}

	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	//-----------------------------------------------------------
	public static void main(String[] args) {
		new Main().run();
	}

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

        public void print1Int(int[] a){
                for(int i = 0; i < a.length; i++)
                        System.out.print(a[i] + " ");
                System.out.println();
        }
        
        public void print2Int(int[][] a){
                for(int i = 0; i < a.length; i++){
                        for(int j = 0; j < a[0].length; j++){
                                System.out.print(a[i][j] + " ");
                        }
                        System.out.println();
                }
        }
        
	public void run() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
                        out = new PrintWriter(System.out);
			tok = null;
			solve();
			in.close();
                        out.close();
		} catch (IOException e) {
			System.exit(0);
		}
	}

	public String nextToken() throws IOException {
		while (tok == null || !tok.hasMoreTokens()) {
			tok = new StringTokenizer(in.readLine());
		}
		return tok.nextToken();
	}

	public int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	public long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	public double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}
        PrintWriter out;
	BufferedReader in;
	StringTokenizer tok;
}