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.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;



public class Brackets{
static class STree {
    pair [] arr,sTree,lazy;
    int N;
    public STree(pair []a)
    {
    	N=a.length-1;
    	
    	arr=a;
    	sTree=new pair[2*N];
    	Arrays.fill(sTree,new pair(0,0,0));
    	lazy=new pair [2*N];
    	build(1,1,N);
    }
    public void build (int node,int b,int e )
    {
    	if(b==e) {
    		sTree[node]=arr[b];}
    	else {
    	int mid = b+e >> 1;
    	build(node<<1,b,mid);
    	build(node<<1| 1,mid+1,e);
//    	System.out.println(node);
    	int d=Math.min(sTree[node<<1|1].c, sTree[node<<1].o);
        int l= sTree[node<<1].o;
        int r= sTree[node<<1|1].c;
        int l2= sTree[node<<1|1].o;
        int r2= sTree[node<<1].c;
        int t1=sTree[node<<1].t;
        int t2=sTree[node<<1|1].t;

    	sTree[node]=new pair(l+l2-d,r+r2-d,t1+t2+d);
    	}
    		
    }
//    public void update_point(int idx , long val)
//    {
//    	int node=idx+N-1;
//    	sTree[node]=val>0?1:val<0?-1:0;
//    	while(node>1)
//    	{
//    		node>>=1;
//    		
//    		
//    	      sTree[node]=sTree[node<<1]*sTree[node<<1|1];
//    	      
//    		   }
//    }
//    public void update_range (int i,int j,long val)
//    {
//    	update_range(1,1,N,i,j,val);
//    }
//    public void update_range(int node,int b,int e,int i,int j,long val)
//    {
//    	if(b>j||e<i)
//    		return;
//    	if(b>=i&&e<=j)
//    	{
//    		sTree[node]+=val*(e-b+1);
//    		lazy[node]+=val;
//    	}else 
//    	{
//    		int mid = b+e >>1;
//    	    propagate(node,b,mid,e);
//    	    update_range(node<<1,b,mid,i,j,val);
//    	    update_range(node<<1|1,mid+1,e,i,j,val);
//    	    sTree[node]=sTree[node<<1]*sTree[node<<1|1];
//
//    	}
//    }
    	
//    public void propagate(int node,int b,int mid ,int e)
//    {
//    	lazy[node<<1]+=lazy[node];
//    	lazy[node<<1|1]+=lazy[node];
//    	sTree[node<<1]+=lazy[node]*(mid-b+1);
//    	sTree[node<<1|1]+=lazy[node]*(e-mid);
//    	lazy[node]=0;
//
//    }
    public pair query(int i,int j)
    {
    	return query(1,1,N,i,j);
    }
    public pair query(int node,int b,int e,int i,int j)
    {
    	if(b>j||e<i)
    		return new pair(0,0,0);
    	if(b>=i&&e<=j)
    		return sTree[node];
    	int mid=b+e >>1;
//    	propagate(node, b, mid, e);
    	pair l=query(node<<1,b,mid,i,j);
    	pair r=query(node<<1|1,mid+1,e,i,j);
    	int d=Math.min(l.o, r.c);
        int l1= l.o;
        int r1= l.c;
        int l2= r.o;
        int r2= r.c;
        int t1=l.t;
        int t2=r.t;   


    	return new pair(l1+l2-d,r1+r2-d,t1+t2+d);
    	
    	
    }
    }
    public static void main(String[] args) throws IOException {
    	
    	PrintWriter pw = new PrintWriter(System.out);
		Scanner sc = new Scanner(System.in); 
        String in=sc.next();
        int n=in.length();
		int m=sc.nextInt();
		int N=1;
        while(N<n)N<<=1;
		pair a[]=new pair [N+1];
		Arrays.fill(a, new pair(0,0,0));
		for(int i=0;i<n;i++) 
		{
			
			if(in.charAt(i)=='(')
			
			    a[i+1]=new pair(1,0,0);
			else
				a[i+1]=new pair(0,1,0);
				
		}
	
			
		STree st=new STree(a);
		StringBuilder s=new StringBuilder("");
		for(int i=0;i<m;i++)
		{
			int l =sc.nextInt();
			int r =sc.nextInt();
			pw.println(st.query(l,r).t*2);
			pw.flush();
		}
	    
		
		}
		

    static class pair
    {
    	int o,c,t;
    	public pair(int o,int c,int t)
    	{
    		this.o=o;
    		this.c=c;
    		this.t=t;
    	}
    	
    }
    static class Scanner {

		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}

		public Scanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public char nextChar() throws IOException {
			return next().charAt(0);
		}

		public Long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
}
