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 «()(())(())».
//TEMPLATE V2
	import java.io.*;
	import java.util.*;
	import java.math.*;
	
public class Main {
//Solution goes below: ------------------------------------
	static class Node{
		int br;
		int op;
		int cl;
		Node(){//Filler node.
			br=0;
			op=0;
			cl=0;
		}
		Node(int b, int o, int c){
			br=b;
			op=o;
			cl=c;
		}
		Node merge(Node other){
			int newpairs = Math.min(this.op,other.cl);
			return(
				new Node(
					this.br+other.br+newpairs,
					this.op+other.op-newpairs,
					this.cl+other.cl-newpairs
				)
			);
		}
	}

	static Node[] tree;

	static Node Go(int level, int pos){
		//This is recursive, and should run in O(log N) time.
		Node n = tree[level+pos];
		int l = (int)(size/level)*pos;
		int r = (int)(size/level)*(pos+1)-1;//I fucking hate rounding errors.

		if(left<=l&&r<right){
			return n;//Yay we're done.
		}else if(r<left || right<=l){
			return new Node();//Nothing to see here...
		}else{
			return Go(level*2,pos*2).merge(Go(level*2,pos*2+1));
		}
	}
	static int size;
	static int left,right;//Query
    public static void solution() throws IOException{
		char[] paren = nextLine().toCharArray();
		size = paren.length==1?1:Integer.highestOneBit(paren.length - 1)*2;
		tree = new Node[size*2];//Segment tree.

		for(int i =0; i<paren.length;i++){
			if(paren[i]=='('){
				tree[size+i]= new Node(0,1,0);
			}else{
				tree[size+i]=new Node(0,0,1);
			}
		}

		for(int i =paren.length; i<size;i++){//FUCK ROUNDING ERRORS
			tree[size+i]=new Node();
		}
		
		for(int i=size-1; i>=1;i--){
			//Takes them two at a time.
			tree[i] = tree[2*i].merge(tree[2*i+1]);
		}
		/*
		for(int i =1; i<size*2;i++){
			Node n=tree[i];
			print(n.br);print(" ");
			print(n.op);print(" ");
			print(n.cl);print(" ");
			println();
			println("----");
			flush();
		}
		*/
		int n = nextInt();
		for(int q=0;q<n;q++){
			left=nextInt()-1;
			right=nextInt();//Not b-1 bc it's inclusive.
			println(2*Go(1,0).br);
		}	
    }

//Solution goes above: ------------------------------------
	public static final String IN_FILE = "";
	public static final String OUT_FILE = "";
//-------------------- ------------------------------------
	//IO
	public static BufferedReader br;
	public static StringTokenizer st;
	public static BufferedWriter bw;
    public static void main(String[] args) throws IOException{
		if(IN_FILE==""){
			br = new BufferedReader(new InputStreamReader(System.in)); 
		}else{
			try {
				br = new BufferedReader(new FileReader(IN_FILE));
			} catch (FileNotFoundException e) {
				e.printStackTrace();
			}
		}
		if (OUT_FILE==""){
			bw = new BufferedWriter(new OutputStreamWriter(System.out));
		}else{
			bw = new BufferedWriter (new FileWriter(OUT_FILE) );
		}
		solution();
		bw.close();//Flushes too.
	}

	public static String nextToken() {
		while (st == null || !st.hasMoreElements()) {
			try {
				st = new StringTokenizer(br.readLine());
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
		return st.nextToken();
	}

	public static String nextLine() {
		st = null;
		try {
			return br.readLine();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return null;
	}

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

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

	public static double nextDouble() {
		return Double.parseDouble(nextToken());
	}
	
	public static void println(Object s) throws IOException{
		bw.write(s.toString()+"\n");
	}
	
	public static void println() throws IOException{
		bw.newLine();
	}

    public static void print(Object s) throws IOException{
		bw.write(s.toString());
	}
	public static void flush() throws IOException{//Useful for debug
		bw.flush();
	}
	//Other
	public static class Arr<T> extends ArrayList<T> {} //I hate typing ArrayList
}