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

public class q4 {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		Reader.init(System.in);
		String s=Reader.next();
		int t=s.length();
		SegmentTree c=new SegmentTree(s,t);
		t--;
		c.build(0, t, 0);
		int q=Reader.nextInt();
		for(int i=0;i<q;i++) {
			int ql=Reader.nextInt()-1;
			int qh=Reader.nextInt()-1;
			N ans=c.anss(0, t,0 , ql, qh);
			System.out.println(2*ans.ans);
		}
		
	}

}
class SegmentTree{
	int[] ans;
	int[] ob;
	int[] cb;
	String s;
	SegmentTree(String a, int n){
		s=a;
		ans=new int[4*n];
		ob=new int[4*n];
		cb=new int[4*n];
	}
	void build(int low,int high,int pos) {
		if(low==high) {
			if(s.charAt(low)=='(') {
				ob[pos]=1;
			}
			else {
				cb[pos]=1;
			}
		}
		else {
			int middle=(low+high)/2;
			build(low,middle,2*pos+1);
			build(middle+1,high,2*pos+2);
			int temp=Math.min(ob[2*pos+1],cb[2*pos+2]);
			ans[pos]=ans[2*pos+1]+ans[2*pos+2]+temp;
			ob[pos]=ob[2*pos+1]+ob[2*pos+2]-temp;
			cb[pos]=cb[2*pos+1]+cb[2*pos+2]-temp;
			
		}
	}
	
	N anss(int low,int high, int pos,int ql,int qh) {
		if(ql>high || qh < low) {
			return new N(0,0,0);
		}
		else if(ql<=low && qh>=high) {
			return new N(ans[pos],ob[pos],cb[pos]);
		}
		else {
			int middle=(low+high)/2;
			N left=anss(low,middle,2*pos+1,ql,qh);
			N right=anss(middle+1,high,2*pos+2,ql,qh);
			int temp=Math.min(left.ob, right.cb);
			int t=left.ans+right.ans+temp;
			int o=left.ob+right.ob-temp;
			int c=left.cb+right.cb-temp;
			return new N(t,o,c);	
		}
	}
}

class N{
	int ans;
	int ob;
	int cb;
	boolean discard;
	N(int a,int b,int c){
		ans=a;ob=b;cb=c;
	}
	
}
class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;
 
    /** call this method to initialize reader for InputStream */
    static void init(InputStream input) {
        reader = new BufferedReader(
                     new InputStreamReader(input) );
        tokenizer = new StringTokenizer("");
    }
 
    /** get next word */
    
    static String next() throws IOException {
        while ( ! tokenizer.hasMoreTokens() ) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(
                   reader.readLine() );
        }
        return tokenizer.nextToken();
    }
 
    static int nextInt() throws IOException {
        return Integer.parseInt( next() );
    }
    static long nextLong() throws IOException {
        return Long.parseLong( next() );
    }
    static double nextDouble() throws IOException {
        return Double.parseDouble( next() );
    }
}