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.util.*;
import java.io.*;

public class Main2 {
	static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
 
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
 
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
 
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
 
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
 
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
 
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
	static FastReader sc = new FastReader();
	static char s[];
	static node seg[];
	public static void main (String[] args) {
		PrintWriter out = new PrintWriter(System.out);
		int t = 1;
//    	t = sc.nextInt();
    	while(t-->0) {
    		s = sc.next().toCharArray();
    		seg = new node[4*s.length];
    		build(0,0,s.length-1);
    		int m = sc.nextInt();
//    		for(int i=0;i<seg.length;i++)
//    			if(seg[i]!=null)
//    			System.out.print(seg[i].full+" ");
//    		System.out.println();System.out.println("------------------");System.out.println();
    		while(m-->0) {
    			int x = sc.nextInt();
    			int y = sc.nextInt();
    			x--; y--;
    			node res = ans(0,0,s.length-1,x,y);
    			out.write((2*res.full)+"\n");
    		}
      	}
		out.close();
	}
	private static node ans(int idx, int low, int high, int x, int y) {
//		System.out.println(low+" "+high);
		if(low == high) {
			if(x<=low && high<=y)
				return seg[idx];
			else
				return new node(0,0,0);
		}
		if(y<low || x>high) return new node(0,0,0);
		if(x<=low && high<=y) return seg[idx];
		
		int mid = (low+high) >> 1;
		
		node left = ans(2*idx+1,low,mid,x,y);
		node right = ans(2*idx+2,mid+1,high,x,y);
		
		int full = left.full + right.full + Math.min(left.open,right.close);
    	int open = left.open + right.open - Math.min(left.open,right.close);
    	int close = left.close + right.close - Math.min(left.open,right.close);
    	
		return new node(open,close,full);
	}
	static void build(int idx,int low,int high) {
		if(low == high) {
			node temp;
			if(s[low] == '(') temp = new node(1,0,0);
			else temp = new node(0,1,0);
			seg[idx] = temp;
			return;
		}
		
		int mid = (low+high) >> 1;
    	
    	build(2*idx+1,low,mid);
    	build(2*idx+2,mid+1,high);
    	
    	node left = seg[2*idx+1];
    	node right = seg[2*idx+2];
    	
    	int full = left.full + right.full + Math.min(left.open,right.close);
    	int open = left.open + right.open - Math.min(left.open,right.close);
    	int close = left.close + right.close - Math.min(left.open,right.close);
    	
    	seg[idx] = new node(open,close,full);
	}
}
class node{
	 int open;
	 int close;
	 int full;
	 node(int open, int close, int full){
		 this.open = open;
		 this.close = close;
		 this.full = full;
	 }
 }