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.Scanner;
import java.io.*;
public class main{
	static int t[],c[],o[];
	public static void main(String []args){
		//Scanner s=new Scanner(System.in);
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pr=new PrintWriter(System.out,true);
		try{
    		String in=br.readLine(),tt[];
    	
    		int m=Integer.parseInt(br.readLine()),l,r;
    		char []a=in.toCharArray();
    		t=new int[3*1000001];
    		c=new int[3*1000001];
    		o=new int[3*1000001];		
    		build(1,0,a.length-1,a);
    		for(int i=0;i<m;i++){
    			tt=br.readLine().split(" ");
    			l=Integer.parseInt(tt[0])-1;
    			r=Integer.parseInt(tt[1])-1;
    			pr.println(2*query(1,0,a.length-1,l,r).t);
    		}

    		br.close();
		}catch (IOException e){
			e.printStackTrace();
		}

	}

	public static void build(int pos,int start,int end,char a[]){
		// if(pos>a.length-1||pos<0)
		// 	return;
		if(end==start){
			if(a[start]=='(')
				c[pos]=1;
			else
				o[pos]=1;
			return ;
		}

		int mid=(start+end)/2;
		build(2*pos,start,mid,a);
		build(2*pos+1,mid+1,end,a);
		int temp=Math.min(c[2*pos],o[2*pos+1]);
		t[pos]=t[2*pos]+t[2*pos+1]+temp;
		o[pos]=o[2*pos]+o[2*pos+1]-temp;
		c[pos]=c[2*pos]+c[2*pos+1]-temp;
	}

	public static int length(int n){
		return 2*n-1;
	}

	public static Pair query(int pos,int start,int end,int l,int r){
		if(l>end||r<start)
			return null;
		if(l<=start&&end<=r)
			return new Pair(t[pos],c[pos],o[pos]);
		int mid=(start+end)/2;
		Pair p1=query(2*pos,start,mid,l,r);
		Pair p2=query(2*pos+1,mid+1,end,l,r);
		
		Pair t;
		if(p1!=null&&p2!=null){
			int temp=Math.min(p1.c,p2.o);
			t=new Pair(p1.t+p2.t+temp,p1.c+p2.c-temp,p1.o+p2.o-temp);
		}
		else if(p1!=null)
			t=p1;
		else
			t=p2;
		return t;
	}


}

class Pair{
	int t;
	int c;
	int o;
	public Pair(int x,int y,int z){
		t=x;
		c=y;
		o=z;
	}
}