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.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;





public class Zad2 {
	

static class Node { 
	
	int numOpened;
	int numClosed;
	int numCorrectSub;
	
	
	public Node(int numOpened, int numClosed, int numCorrectSub) { 
		this.numOpened = numOpened;
		this.numClosed = numClosed; 
		this.numCorrectSub = numCorrectSub;
	}
	
	public Node() { 
		
	}
}

static class ModSegmentTree 
{
    Node tree[]; // nizata koja ja pretstavuva 'fizichkata' reprezentacija na drvoto
 
    ModSegmentTree(String str)
    {
    	int N = str.length();
    	
    	
        // visinata na drvoto
        int x = (int) (Math.ceil(Math.log(N) / Math.log(2)));
 
        // kolku elementi se potrebni vo drvoto ~ 2*N - 1
        int max_size = 2 * (int) Math.pow(2, x) - 1;
 
        
        
        tree = new Node[max_size]; // Memory allocation
 
        // ja povikuvame pomoshnata funkcija za kreiranje na segmentnoto drvo
        constructSegmentTree(str, 0, N - 1, 0);
    }
    
    // rekurzivna funkcija za gradenje na segmentnoto drvo 
    
    // @arr - nizata spored koja se modelira segmentnoto drvo
    // @begin - pochetokot na intervalot za kojshto e odgovoren tekovniot jazel vo rekurzijata
    // @end - krajot na intervalot za kojshto e odgovoren tekovniot jazel vo rekurzijata
    // @treeNode - indeksot na tekovniot jazel vo rekurzijata
    
    Node constructSegmentTree(String str, int begin, int end, int treeNode)
    {
        // dokolku sme stignale do list od drvoto (jazel koj e odgovoren samo za eden element)
    	// sumata na toj interval e trivijalna, odnosno sumata e samiot toj element
        if (begin == end) {
            if(str.charAt(begin) == '(') { 
            	tree[treeNode] = new Node(1, 0, 0);
            } else { 
            	tree[treeNode] = new Node(0, 1, 0);
            }
            return tree[treeNode];
        }
 
        // Dokolku sme vo vnatresen jazel, sumata na toj jazel e zbirot od sumata na levoto dete-jazel
        // i sumata na desnoto dete-jazel
        int mid = getMid(begin, end);
        
        Node leftChild = constructSegmentTree(str, begin, mid, 2*treeNode+ 1);
        Node rightChild =  constructSegmentTree(str, mid + 1, end, 2*treeNode + 2);
        
        int temp = Math.min(leftChild.numOpened, rightChild.numClosed);
        
        Node newNode = new Node();
        
        newNode.numCorrectSub = leftChild.numCorrectSub + rightChild.numCorrectSub + temp;
        newNode.numOpened = leftChild.numOpened + rightChild.numOpened - temp;
        newNode.numClosed = leftChild.numClosed + rightChild.numClosed - temp;
        
        tree[treeNode] = newNode;
        return tree[treeNode];
    }
 
    // pomoshna funkcija za presmetuvanje na sredisniot indeks za daden interval
    
    // @s - pochetok na intervalot
    // @e - kraj na intervalot
    int getMid(int s, int e) {
        return s + (e - s) / 2;
    }


     
    public Node getSol(int begin, int end, int queryBegin, int queryEnd, int treeNode) { 
    	
    	if(begin > queryEnd) return new Node(0, 0, 0);
    	if(end < queryBegin) return new Node(0,0,0);
    	
    	if(begin >= queryBegin && end <= queryEnd) return tree[treeNode];
    	
    	
    	int mid = (begin + end) / 2;
    	Node leftChild = getSol(begin, mid, queryBegin, queryEnd, 2 * treeNode + 1);
    	Node rightChild = getSol(1 + mid, end, queryBegin, queryEnd, 2 * treeNode + 2);
    	

    	
    	int temp = Math.min(leftChild.numOpened, rightChild.numClosed);
    	
    	int corr = leftChild.numCorrectSub + rightChild.numCorrectSub + temp;
    	int o = leftChild.numOpened + rightChild.numOpened - temp;
    	int c = leftChild.numClosed + rightChild.numClosed - temp;
    	
    	return new Node(o,c,corr);
    }
   
 
}
	
	
	public static void main(String [] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer tokenizer;
		String s = br.readLine();
		
		int numQueries = Integer.parseInt(br.readLine());
		
		
		ModSegmentTree tree = new ModSegmentTree(s);
		for(int i=0; i<numQueries; i++) { 
			
			tokenizer = new StringTokenizer(br.readLine());
			
			int from = Integer.parseInt(tokenizer.nextToken());
			int to	 = Integer.parseInt(tokenizer.nextToken());
			
			Node sol = tree.getSol(0, s.length()-1, from-1, to-1, 0);
			
			bw.write("" + 2*sol.numCorrectSub);
			bw.newLine();
		}
		
		bw.flush();
		bw.close();
		
	}

}
