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.*;
import java.util.*;
 
import javax.sound.midi.Synthesizer;
import javax.swing.plaf.synth.SynthSpinnerUI;
 
 
 
public class Main {
	
	
	static Scanner sc=new Scanner(System.in);
	static PrintWriter out=new PrintWriter(System.out);
	
	static  int[] memo;
    static int N;
    static int x[];
    static int y[];
    static int a[];
    static int sign[];
	static int mat[][];
	
    public static void main(String [] args) throws IOException, InterruptedException {
 
		char[] s = sc.next().toCharArray();
		int q=sc.nextInt();
		int x[]=new int[s.length+1];
		for (int i = 1; i <=s.length; i++) {
			x[i]=s[i-1]=='('?1:0;
		}
		SegmentTree st=new SegmentTree(x);
		while(q-->0) {
			System.out.println(2*st.query(sc.nextInt(), sc.nextInt()).valid);
		}
}
    static class edge{
    	long valid;
    	long open;
    	long closed;
    	public edge(long sTree,long open2,long closed2) {
		valid=sTree;
		open=open2;
		closed=closed2;
    	}
    	
    }
 
//static final int INF = (int)1e9;
   
    static class Pair{
    	int val;
    	int count;
     Pair(int v,int c) {
    		val=v;
    		count=c;
    	}
    }
    static  boolean visited[];
    static int INF=(int) 1e9;
    static int ans=INF;
public static void dp(int n,int m,int count) {
    	    
    }
    
/**    static long dp1(int i,int j) {
    	if(i==j) {
    		return 0;
    	}
    	if(memo[i][j] != -1)
			return memo[i][j];
    	long min=INF;
    	for (int j2 = i; j2 < j; j2++) {
			min=Math.min(min, dp1(i,j2)+dp1(j2+1,j)+mat[i][0]*mat[j2][1]*mat[j][1]);
		}
    	return memo[i][j]=min;
    }
    static StringBuilder sb;
    static void trace(int i ,int j) {
    if(i==j) {
    	sb.append("A");
    	sb.append(i+1);
    }
    
   long ans= dp1(i,j);
   for (int j2 = i; j2 < j; j2++) {
		
    if(ans==dp1(i,j2)+dp1(j2+1,j)+mat[i][0]*mat[j2][1]*mat[j][1]){
    sb.append("(");
    trace(i,j2);
    sb.append(" "+"x"+" ");
   trace(j2+1, j);
    sb.append(")");
    return;
    }
    }
    }
	static int[] lis(int[] a, int n, boolean inc)
	{
		int[] L = new int[n];
		for (int i = 0; i < L.length; i++) {
			L[i]=1;
		}
		for(int i = n - 1; i >= 0; --i)
		{
			for(int j = n - 1; j > i; --j)
				if((inc && a[j] > a[i] || !inc && a[j] < a[i]) && L[j] + 1 > L[i])
					L[i] = L[j] + 1;
		}
		return L;
	}
	public static int[] lisn2(int a[],int n,boolean f) {
		int lis[]=new int[n+1];
			lis[0]=1;
		
		for (int i = 1; i < a.length; i++) {
			for (int j = 0; j <i; j++) {
			if((f&&a[i]>a[j]||!f&&a[i]<a[j])&&lis[i]<lis[j]+1) {
				lis[i]=lis[j];
			}
			}
			lis[i]++;
		}
		return lis;
	}
	 static int[] lis3(int arr[],int n,boolean f) 
	    { 
	          int lis[] = new int[n]; 
	          int i,j,max = 0; 
	  
	          /* Initialize LIS values for all indexes 
	  lis[0]=1;
	           /* Compute optimized LIS values in bottom up manner */
	    /**       for ( i = 1; i < n; i++ ) 
	              for ( j = 0; j < i; j++ )  
	                         if (((f&& arr[i] > arr[j] )||!f&&arr[j]>arr[i])&& lis[i] < lis[j] + 1) 
	                    lis[i] = lis[j] + 1; 
	  
	  
	            return lis; 
	    } 
	
	public static int dp(int high,int low,int i) {
		if(i==N) {
			return 0;
		}
		int take=0;
		int leave=0;
		
		if(a[i]>high) {
			take+=1+dp(a[i],low,i+1);
		}
		else if(a[i]<low) {
		take+=1+dp(high,a[i],i+1);
		}
		
		leave=dp(high,low,i+1);
		return Math.max(leave, take);
	
	}
 
 
	
	
	static int lis(int[] A, int n)		// Can be implemented with TreeSet (lower, remove, add)
	{
		ArrayList<Integer> L = new ArrayList<Integer>(); 
		int[] P = new int[n];			
		int[] L_id = new int[n];
		lis2=new int[n];
		int lis = 0, lis_end = -1;
		for(int i = n-1; i >=0; i--) 
		{
			int pos = Collections.binarySearch(L, A[i]);
			if (pos < 0) pos = -(pos + 1);
 
			if(pos >= L.size()) L.add(A[i]);
			else                 L.set(pos, A[i]);
 
			if(pos + 1 > lis)
			{
				lis = pos + 1;
				lis_end = i;
			}
			
			//lis_end and the following part for printing the solution
			L_id[pos] = i;
			P[i] = pos > 0 ? L_id[pos-1] : -1;
	       lis2[i]=pos;
		}
		
		stack = new Stack<Integer>();
		while(lis_end != -1)
		{
			stack.push(A[lis_end]);
			lis_end = P[lis_end];
		}
		while(!stack.isEmpty()) {
			
			l2.add(stack.pop());
			}
		return lis;
	}
	static int lis1[];
	static int lis2[];
	
	/**static int lis1(int[] A, int n)		// Can be implemented with TreeSet (lower, remove, add)
	{
		lis1=new int[n];
		ArrayList<Integer> L = new ArrayList<Integer>(); 
		int[] P = new int[n];			
		int[] L_id = new int[n];
		
		int lis = 0, lis_end = -1;
		for(int i = 0; i <n; i++) 
		{
			int pos = Collections.binarySearch(L, A[i]);
			if (pos < 0) pos = -(pos + 1);
 
			if(pos >= L.size()) L.add(A[i]);
			else                 L.set(pos, A[i]);
 
			if(pos + 1 > lis)
			{
				lis = pos + 1;
				lis_end = i;
			}
			lis1[i]=pos;
			L_id[pos] = i;
			P[i] = pos > 0 ? L_id[pos-1] : -1;
		}
	
		first=lis_end;
		stack = new Stack<Integer>();
		
		return lis;
	}
	static int first;
	static ArrayList<Integer> l1=new ArrayList<>();
	static ArrayList<Integer> l2=new ArrayList<>();
	
	static Stack<Integer> stack;	
	private static int binary(int h, ArrayList<Integer> l) {
	int low=0;
	int high=l.size();
	int ans=-1;
	while(high>=low) {
		int mid=(high+low)>>1;
		if(mid!=l.size()&&l.get(mid)>h) {
			ans=mid;
			high=mid-1;
		}
		else {
			low=mid+1;
		}
		
	}
	return ans;
	
	}
 
	
 
	static class doll  implements Comparable<doll>{
		int h;
		int w;
		doll(int h1,int w1){
		h=h1;
		w=w1;
		}
		@Override
		public int compareTo(doll d) {
			if(h!=d.h) {
				return d.h-h;
			}
			return w-d.w;
		}
		
		}
	
		
		
		
		
	
    static HashSet<Integer> set=new HashSet<>();
	static ArrayList<Integer> end;
	static int score[];
	static int INF=(int) 1e9;
	**/   
	static  class Scanner {
	StringTokenizer st;
	BufferedReader br;
 
	public Scanner(InputStream s) {
		br = new BufferedReader(new InputStreamReader(s));
	}
 
	public String next() throws IOException {
		while (st == null || !st.hasMoreTokens())
			st = new StringTokenizer(br.readLine());
		return st.nextToken();
	}
 
	public int nextInt() throws IOException {
		return Integer.parseInt(next());
	}
 
	public int[] nextIntArr(int n) throws IOException {
		int[] arr = new int[n];
		for (int i = 0; i < n; i++)
			arr[i] = nextInt();
		return arr;
	}
 
	public long[] nextLongArr(int n) throws IOException {
		long[] arr = new long[n];
		for (int i = 0; i < n; i++)
			arr[i] = nextLong();
		return arr;
	}
 
	public long nextLong() throws IOException {
		return Long.parseLong(next());
	}
 
	public String nextLine() throws IOException {
		return br.readLine();
	}
 
	public double nextDouble() throws IOException {
		return Double.parseDouble(next());
	}
 
	public boolean ready() throws IOException {
		return br.ready();
	}
	public void waitForInput() throws InterruptedException {Thread.sleep(2500);}
}
 
static class SegmentTree {
	private static final long INF = (long) 1E15;
	int N; // number of elements in my array after the padding
	int [] array;
	long []sTree, lazy,open,closed; 
	SegmentTree(int[] a){
		N=1;
	  int n=a.length;
		while(n>N) {
			N=N<<1;
		}
		array=a;
		closed=new long[N<<1];
		open=new long[N<<1];
		sTree =  new long[N<<1];
		lazy =  new long[N<<1];
		build(1, 1, N);
	}
	void build(int node, int b, int e) {
		if(b == e) {
			
		if(b<array.length&&array[b]==1) {
			open[node]=1;
		}
		else if(b<array.length&&array[b]==0){
			closed[node]=1;
		}
		}
		else {
			int nodeLeft = node << 1;
			int nodeRight = (node << 1)+1;
			int mid = (b + e) >> 1;
			build(nodeLeft, b , mid);
			build(nodeRight, mid + 1, e);
			long min=Math.min(open[nodeLeft],closed[nodeRight]);
			sTree[node]=sTree[nodeLeft]+sTree[nodeRight]+min;
			open[node]=open[nodeLeft]+open[nodeRight]-min;
			closed[node]=closed[nodeLeft]+closed[nodeRight]-min;
			}
	}
		
	
	
	// add value v for element in position idx in my input array
	//O(log(N))
	void update_point(int idx, long v) {
		int node = idx + N - 1;
		if(sTree[node] != 0)
			return;
		sTree[node] = v;
		while(node > 1) {
			node >>= 1;
		sTree[node] = Math.max(sTree[node<<1],sTree[node<<1|1]);
		
			}
 
		
		
		
	}
	// O(log(N))
	edge query(int i, int j) {
		return query(1, 1, N, i, j); 
	}
	edge query(int node, int b, int e, int i, int j) {
		
	    if(i > e || j < b)
			return null;
		if(b >= i && e <= j)
			return new edge(sTree[node],open[node],closed[node]);
		int mid = (b + e) >> 1;
		edge q1 = query(node << 1, b, mid, i , j);
		edge q2= query(node<<1|1, mid + 1, e, i, j);
		if(q1==null) {
			return q2;
		}
		if(q2==null) {
			return q1;
		}
		long op=q1.open;
		long cl=q2.closed;
		long min=Math.min(op,cl);
			return new edge(q1.valid+q2.valid+min,q1.open+q2.open-min,q1.closed+q2.closed-min);
	
		
		
	}
	void propagate(int node, int b, int e) {
		int leftChild = node << 1;
		int rightChild = node<<1|1;
		
		lazy[leftChild] += lazy[node];
		lazy[rightChild] += lazy[node];
		sTree[leftChild] +=  lazy[node];
		sTree[rightChild] +=lazy[node];
		
		lazy[node] = 0;
	}
	void update_range(int i, int j, int val) { //O(log(N))In
		update_range(1, 1, N, i, j, val); 
	}
	void update_range(int node, int b, int e, int i, int j, int val) {
		if(i > e || j < b)
			return;
		if(b >= i && e <= j) {
			sTree[node] += val;
			lazy[node] += val;
		}
		else {
			int mid = (b + e) >> 1;
		propagate(node, b, e);	
		update_range(node<<1, b , mid, i, j, val);
			update_range(node<<1|1, mid+1, e, i, j, val);
			sTree[node] = Math.min(sTree[node<<1] , sTree[node<<1|1]);
		}
	}
 
}
}