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 java.math.*;
public class spoj {
    InputStream is;
    PrintWriter out; 
	static AbeySaale segTree[];
	static char ch[];
	
	static class AbeySaale
	{
		int ans;
		int open;
		int close;
		
		AbeySaale(int a,int o,int c)
		{
			ans=a;open=o;close=c;
		}
		
	}
	
	public static void build(int pos,int l,int r)
	{
		if(l==r)
		{
			if(ch[l]=='(')
				segTree[pos]=new AbeySaale(0,1,0);
			else if(ch[l]==')')
				segTree[pos]=new AbeySaale(0,0,1);
			return;
		}
		
		int m=(l+r)/2;
		build(2*pos+1,l,m);
		build(2*pos+2,m+1,r);
		segTree[pos]=new AbeySaale(0,0,0);
		segTree[pos].ans=segTree[2*pos+1].ans+segTree[2*pos+2].ans+Math.min(segTree[2*pos+1].open,segTree[2*pos+2].close);
		segTree[pos].open=segTree[2*pos+1].open+segTree[2*pos+2].open-Math.min(segTree[2*pos+1].open,segTree[2*pos+2].close);
		segTree[pos].close=segTree[2*pos+1].close+segTree[2*pos+2].close-Math.min(segTree[2*pos+1].open,segTree[2*pos+2].close);
		
	}
	
	public static AbeySaale query(int pos,int l,int r,int qs,int qe)
	{
		if(l>r)
			return new AbeySaale(0,0,0);
		
		if(qs>r || qe<l)
			return new AbeySaale(0,0,0);
		if(l>=qs && r<=qe)
		{
			return segTree[pos];
		}
		
		int m=(l+r)/2;
		AbeySaale aa=query(2*pos+1,l,m,qs,qe);
		AbeySaale bb=query(2*pos+2,m+1,r,qs,qe);
		
		int t;
		t=Math.min(aa.open,bb.close);
		return new AbeySaale(aa.ans+bb.ans+t,aa.open+bb.open-t,aa.close+bb.close-t);
	}
	
	
    void solve()
    {
		ch=ns().toCharArray();
		int n=ch.length;
		segTree=new AbeySaale[4*n];
		
		build(0,0,n-1);
		//out.println(segTree[0].ans+" "+segTree[0].open+" "+segTree[0].close);
		int m=ni();
		while(m-->0)
		{
			AbeySaale op=query(0,0,n-1,ni()-1,ni()-1);
			out.println((op.ans)*2);
		}
		
		
		
	}
	
	
	
	
	
	
 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	
	
 
 
	  
	  
	  
	
    //---------- I/O Template ----------
    
    public static void main(String[] args) { new spoj().run(); }
    void run() { 
        is = System.in; 
        out = new PrintWriter(System.out);
        solve();
        out.flush();
    }
    
    byte input[] = new byte[1024];
    int len = 0, ptr = 0;
    
    int readByte() { 
        if(ptr >= len) { ptr = 0; 
            try { len = is.read(input); } 
            catch(IOException e) { throw new InputMismatchException(); } 
            if(len <= 0) { return -1; } 
        } return input[ptr++];
    }
    boolean isSpaceChar(int c) { return !( c >= 33 && c <= 126 ); }
    int skip() { 
        int b = readByte(); 
        while(b != -1 && isSpaceChar(b)) { b = readByte(); } 
        return b;
    }
    
    char nc() { return (char)skip(); }
    String ns() { 
        int b = skip(); 
        StringBuilder sb = new StringBuilder(); 
        while(!isSpaceChar(b)) { sb.appendCodePoint(b); b = readByte(); } 
        return sb.toString();
    }
    String nLine() { 
        int b = skip(); 
        StringBuilder sb = new StringBuilder(); 
        while( !(isSpaceChar(b) && b != ' ') ) { sb.appendCodePoint(b); b = readByte(); } 
        return sb.toString();
    }
    int ni() { 
        int n = 0, b = readByte(); 
        boolean minus = false; 
        while(b != -1 && !( (b >= '0' && b <= '9') || b == '-')) { b = readByte(); } 
        if(b == '-') { minus = true; b = readByte(); } 
        if(b == -1) { return -1; }  //no input 
        while(b >= '0' && b <= '9') { n = n * 10 + (b - '0'); b = readByte(); } 
        return minus ? -n : n;
    }
    long nl() { 
        long n = 0L;    int b = readByte(); 
        boolean minus = false; 
        while(b != -1 && !( (b >= '0' && b <= '9') || b == '-')) { b = readByte(); } 
        if(b == '-') { minus = true; b = readByte(); } 
        while(b >= '0' && b <= '9') { n = n * 10 + (b - '0'); b = readByte(); } 
        return minus ? -n : n;
    }
 
    double nd() { return Double.parseDouble(ns()); }
    float nf() { return Float.parseFloat(ns()); }
    int[] na(int n) { 
        int a[] = new int[n]; 
        for(int i = 0; i < n; i++) { a[i] = ni(); } 
        return a;
    }
    char[] ns(int n) { 
        char c[] = new char[n]; 
        int i, b = skip(); 
        for(i = 0; i < n; i++) { 
            if(isSpaceChar(b)) { break; } 
            c[i] = (char)b; b = readByte(); 
        } return i == n ? c : Arrays.copyOf(c,i);
    }
	void pa(int a[])
	{
		for(int i=0;i<a.length;i++)
		out.print(a[i]+" ");
		out.println();
	}
	
}