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.io.OutputStream;
import java.io.PrintWriter;
import java.math.BigInteger;


import java.util.*;
import java.util.stream.IntStream;
public class random_num {
public static long m=(long) (Math.pow(10,9)+7);
static int size=1000001;
public static int a[]=new int[3*size];
public static Pair tree[]=new Pair[3*size];
	public static void main(String args[]){
		InputReader s= new InputReader(System.in);
		OutputStream outputStream= System.out;
		PrintWriter out= new PrintWriter(outputStream);
		for(int i=0;i<3*size;i++){
			tree[i]=new Pair(0,0);
		}
		String str=s.nextLine();
		for(int i=0;i<str.length();i++){
			if(str.charAt(i)=='(')
				a[i]=1;
			else
				a[i]=-1;
		}
		buildSegTree(1,0,str.length()-1);
		int m=s.nextInt();
		for(int i=0;i<m;i++){
			int l=s.nextInt();
			int r=s.nextInt();
			out.println(2*findMax(1,0,str.length()-1,l-1,r-1).c);
		}
		
		out.close();
		
	}
	public static void buildSegTree(int node, int l, int r){
		if(l==r){
			if(a[l]==1){
				tree[node].x++;
			}
			else{
				tree[node].y++;
			}
		}
		else{
			int mid=(l+r)/2;
			buildSegTree(2*node, l, mid);
	        buildSegTree(2*node+1, mid+1, r);
	        tree[node] = mergePair(tree[node*2],tree[node*2+1]);
		}
	}
	public static Pair mergePair(Pair one, Pair two){
		Pair ret=null;
		if(one!=null && two!=null){
			ret=new Pair(one.x+two.x,one.y+two.y);
			ret.c=Math.min(one.x,two.y)+one.c+two.c;
			ret.x-=Math.min(one.x,two.y);
			ret.y-=Math.min(one.x,two.y);
		}
		else if(one!=null)
			ret=one;
		else if(two!=null)
			ret=two;
		return ret;
	}
	
	public static Pair findMax(int node, int start, int end, int l, int r)
	{
	    if(r < start || end < l)
	    {
	        return null;
	    }
	    if(l <= start && end <= r)
	    {
	        return tree[node];
	    }
	    int mid = (start + end) / 2;
	    Pair p1 = findMax(2*node, start, mid, l, r);
	    Pair p2 = findMax(2*node+1, mid+1, end, l, r);
	    return mergePair(p1,p2);
	}
	
	static class Pair {
		long x;
		long y;
		long c=0;
		Pair(long xx,long yy){
			x=xx;
			y=yy;
		}
	}
	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());
	    }
	  }
	public static int gcd(int number1, int number2) {  
		if(number2 == 0){
			return number1;
		} 
		return gcd(number2, number1%number2); 
	}
	public static int combinations(int n,int r){
		if(n==r) return 1;
		if(r==1) return n;
		if(r==0) return 1;
		return combinations(n-1,r)+ combinations(n-1,r-1);
	}
	public static long binomialCoeff(int n, int k)
	{
	    long C[][]= new long[n+1][k+1];
	    int i, j;
	 
	    // Caculate value of Binomial Coefficient in bottom up manner
	    for (i = 0; i <= n; i++)
	    {
	        for (j = 0; j <= Math.min(i, k); j++)
	        {
	            // Base Cases
	            if (j == 0 || j == i)
	                C[i][j] = 1;
	 
	            // Calculate value using previosly stored values
	            else
	                C[i][j] = C[i-1][j-1] + C[i-1][j];
	        }
	    }
	 
	    return C[n][k];
	}
	public static long expo(long a, long b){
	    if (b==1)
	        return a;
	    if (b==2)
	        return a*a;

	    if (b%2==0){
	            return expo(expo(a,b/2),2);
	    }
	    else{
	        return a*(expo(expo(a,(b-1)/2),2));
	    }
	}
	
	public static void sieve(int N){
		int arr[]= new int[N+1];
		for(int i=2;i<Math.sqrt(N);i++){
			if(arr[i]==0){
				for(int j= i*i;j<= N;j= j+i){
					arr[j]=1;
				}
			}
		}
		// All the i for which arr[i]==0 are prime numbers.
	}
	

}