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 «()(())(())».
/*
 * Code Author: Akshay Miterani
 * DA-IICT
 */
import java.io.*;
import java.util.*;


public class SegTree {

	static int n;
	static int N,len;
	static final int size=1000001;
	static double eps=1e-6;
	static Pair tree[]=new Pair[3*size];	
	//static long lazy[]=new long[4*size];
	static int A[]=new int[3*size];
	public static void main(String args[]){
		InputReader in = new InputReader(System.in);
		OutputStream outputStream = System.out;
		PrintWriter out = new PrintWriter(outputStream);
		//----------My Code Starts Here----------
		for(int i=0;i<3*size;i++){
			tree[i]=new Pair(0,0);
		}
		String s=in.nextLine();
		n=s.length();
		for(int i=0;i<s.length();i++){
			if(s.charAt(i)=='(')
				A[i]=1;
			else
				A[i]=-1;
		}
		build(1, 0, n-1);
		N=(int)Math.pow(2,Math.ceil((Math.log(n)/Math.log(2))));
		int m=in.nextInt();
		/*
		for(int i=1;i<2*N;i++){
			out.println(tree[i].x+" "+i);
		}
		*/
		for(int i=0;i<m;i++){
			int l=in.nextInt()-1;
			int r=in.nextInt()-1;
			out.println(query(1, 0, n-1, l, r).c<<1);
		}
		out.close();
		//---------------The End------------------
	}
	//========Segment Tree===========
	static void build(int node, int start, int end)
	{
	    if(start == end)
	    {
	        // Leaf node will have a single element
	    	if(A[start]==1)
	    		tree[node].x++;
	    	else
	    		tree[node].y++;
	    }
	    else
	    {
	        int mid = (start + end) / 2;
	        // Recurse on the left child
	        build(2*node, start, mid);
	        // Recurse on the right child
	        build(2*node+1, mid+1, end);
	        // Internal node will have the sum of both of its children
	        
	        tree[node] = combine(tree[node*2],tree[node*2+1]);
	    }
	}
	static void update(int node, int start, int end, int idx, long val)
	{
	    if(start == end)
	    {
	        // Leaf node
	        A[idx] += val;
	        tree[node].x += val;
	    }
	    else
	    {
	        int mid = (start + end) / 2;
	        if(start <= idx && idx <= mid)
	        {
	            // If idx is in the left child, recurse on the left child
	            update(2*node, start, mid, idx, val);
	        }
	        else
	        {
	            // if idx is in the right child, recurse on the right child
	            update(2*node+1, mid+1, end, idx, val);
	        }
	        // Internal node will have the sum of both of its children
	        tree[node] = combine(tree[node*2],tree[node*2+1]);
	    }
	}
	static Pair query(int node, int start, int end, int l, int r)
	{
	    if(r < start || end < l)
	    {
	        // range represented by a node is completely outside the given range
	        return null;
	    }
	    if(l <= start && end <= r)
	    {
	        // range represented by a node is completely inside the given range
	        return tree[node];
	    }
	    // range represented by a node is partially inside and partially outside the given range
	    int mid = (start + end) / 2;
	    Pair p1 = query(2*node, start, mid, l, r);
	    Pair p2 = query(2*node+1, mid+1, end, l, r);
	    return combine(p1,p2);
	}
	static Pair combine(Pair Left,Pair Right){
		Pair ret=null;
		if(Left!=null && Right!=null){
			ret=new Pair(Left.x+Right.x,Left.y+Right.y);
			long tx=ret.x,ty=ret.y;
			ret.c=Math.min(Left.x,Right.y)+Left.c+Right.c;
			ret.x-=Math.min(Left.x,Right.y);
			ret.y-=Math.min(Left.x,Right.y);
		}
		else if(Left!=null)
			ret=Left;
		else if(Right!=null)
			ret=Right;
		return ret;
	}
	/*
	//===========Lazy Updates========
	static void updateRange(int node, int start, int end, int l, int r, long val)
	{
		
	    if(lazy[node] != 0)
	    { 
	        // This node needs to be updated
	        //tree[node].x += (end - start + 1) * lazy[node];    // Update it
	    	if(tree[node].x!=-1)
	    		tree[node].x=lazy[node]&tree[node].x;
	    	else
	    		tree[node].x=lazy[node];
	    	if(tree[node].x!=(tree[node].x&val))
	    		alright=false;
	    	if(start != end)
	        {
	    		if(lazy[node*2]==0)
	    			lazy[node*2] =val;
	    		else
	    			lazy[node*2]&=val;
	    		if(lazy[node*2+1]==0)
	    			lazy[node*2+1] =val;
	    		else
	    			lazy[node*2+1]&=val;               // Mark child as lazy
	        }
	        lazy[node] = 0;                                  // Reset it
	    }
	    
	    if(start > end || start > r || end < l)              // Current segment is not within range [l, r]
	        return;
	    //System.out.println(start+" "+end+" "+l+" "+r);
	    if(start >= l && end <= r)
	    {
	        // Segment is fully within range
	        //tree[node].x += (end - start + 1) * val;
	    	if(tree[node].x==-1)
	    		tree[node].x=val;
	    	if(tree[node].x!=(tree[node].x&val))
	    		alright=false;
	    	else
	    		tree[node].x=tree[node].x&val;
	    	if(start != end)
	        {
	            // Not leaf node
	    		if(lazy[node*2]==0)
	    			lazy[node*2] =val;
	    		else
	    			lazy[node*2]&=val;
	    		if(lazy[node*2+1]==0)
	    			lazy[node*2+1] =val;
	    		else
	    			lazy[node*2+1]&=val;
	        }
	        return;
	    }
	    int mid = (start + end) / 2;
	    updateRange(node*2, start, mid, l, r, val);        // Updating left child
	    updateRange(node*2 + 1, mid + 1, end, l, r, val);   // Updating right child
	    tree[node] =combine(tree[node*2],tree[node*2+1]);        // Updating root with max value 
	}
	static Pair queryRange(int node, int start, int end, int l, int r)
	{
	    if(start > end || start > r || end < l)
	        return null;         // Out of range
	    if(lazy[node] != 0)
	    {
	        // This node needs to be updated
	       // tree[node].x += (end - start + 1) * lazy[node];            // Update it
	    	if(tree[node].x==-1)
	    		tree[node].x=lazy[node];
	    	if(tree[node].x!=(tree[node].x&lazy[node]))
	    		alright=false;
	    	
	    	if(start != end)
	    	{
	            lazy[node*2] =lazy[node];                  // Mark child as lazy
	            lazy[node*2+1] =lazy[node];                // Mark child as lazy
	        }
	        lazy[node] = 0;                 // Reset it
	    }
	    if(start >= l && end <= r)             // Current segment is totally within range [l, r]
	        return tree[node];
	    int mid = (start + end) / 2;
	    Pair p1 = queryRange(node*2, start, mid, l, r);         // Query left child
	    Pair p2 = queryRange(node*2 + 1, mid + 1, end, l, r); // Query right child
	    return combine(p1,p2);
	}
	static void pushDown(int node, int start, int end){
		if(start==end){
			if(lazy[node]!=0)
				tree[node].x=lazy[node];
			if(tree[node].x==-1)
				tree[node].x=0;
			lazy[node]=0;
			return;
		}
		if(lazy[node] != 0)
		    {
		        // This node needs to be updated
		        //tree[node].x += (end - start + 1) * lazy[node];            // Update it
		        tree[node].x=lazy[node];
				if(start != end)
		        {
		            lazy[node*2] = lazy[node];         // Mark child as lazy
		            lazy[node*2+1] = lazy[node];    // Mark child as lazy
		        }
		        lazy[node] = 0;                 // Reset it
		    }
		 int mid = (start + end) / 2;
		 pushDown(node*2, start, mid);         // Pushing Left Down
		 pushDown(node*2 + 1, mid + 1, end);
	}
	*/
	//===============================
	static class Pair implements Comparable<Pair>{
		long x;
		long y;
		long c=0;
		Pair(long xx,long yy){
			x=xx;
			y=yy;
		}
		@Override
		public int compareTo(Pair o) {
			return Long.compare((this.x),(o.x));
		}
	}
	
	static class InputReader {
	    public BufferedReader reader;
	    public StringTokenizer tokenizer;

	    public InputReader(InputStream inputstream) {
	      reader = new BufferedReader(new InputStreamReader(inputstream));
	      tokenizer = null;
	    }
	    
	    public String nextLine(){
	    	String fullLine=null;
	    	while (tokenizer == null || !tokenizer.hasMoreTokens()) {
	            try {
	              fullLine=reader.readLine();
	            } catch (IOException e) {
	              throw new RuntimeException(e);
	            }
	            return fullLine;
	          }
	          return fullLine;
	    }
		public String next() {
	      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
	        try {
	          tokenizer = new StringTokenizer(reader.readLine());
	        } catch (IOException e) {
	          throw new RuntimeException(e);
	        }
	      }
	      return tokenizer.nextToken();
	    }
		public long nextLong() {
		      return Long.parseLong(next());
		    }
	    public int nextInt() {
	      return Integer.parseInt(next());
	    }
	  }
}