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 Solution {
	public static void main (String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out); 
		
		String str=br.readLine();
		SegmentTree segTree=new SegmentTree(str);
		int q=Integer.parseInt(br.readLine());
		while(q-->0){
		    String[] temp=br.readLine().trim().split(" ");
		    int l=Integer.parseInt(temp[0])-1;
		    int r=Integer.parseInt(temp[1])-1;
		    out.println(segTree.query(l,r));
		}
		out.flush(); 
        out.close(); 
	}
}

class SegmentTree
{
    private Triplet[] tree;
    private int n;
    public SegmentTree(String str){
        this.n=str.length();
        tree=new Triplet[4*n+1];
        for(int i=0;i<tree.length;i++){
            tree[i]=new Triplet();
        }
        buildTree(1,0,n-1,str);
    }
    private void buildTree(int treeNodeIndex,int start,int end,String str){
        if(start==end){
            tree[treeNodeIndex].maxSubsequenceLength=0;
            if(str.charAt(start)=='('){
                tree[treeNodeIndex].numOpeningUnbalanced=1;
            }
            else{
                tree[treeNodeIndex].numClosingUnbalanced=1;
            }
            return;
        }
        int mid=(start+end)/2;
        buildTree(treeNodeIndex*2,start,mid,str);
        buildTree(treeNodeIndex*2+1,mid+1,end,str);
        tree[treeNodeIndex].maxSubsequenceLength=tree[treeNodeIndex*2].maxSubsequenceLength+tree[treeNodeIndex*2+1].maxSubsequenceLength;
        int leftHalfOpeningUnbalanced=tree[treeNodeIndex*2].numOpeningUnbalanced;
        int rightHalfOpeningUnbalanced=tree[treeNodeIndex*2+1].numOpeningUnbalanced;
        
        int leftHalfClosingUnbalanced=tree[treeNodeIndex*2].numClosingUnbalanced;
        int rightHalfClosingUnbalanced=tree[treeNodeIndex*2+1].numClosingUnbalanced;
        
        if(leftHalfOpeningUnbalanced>rightHalfClosingUnbalanced)
        {
            tree[treeNodeIndex].maxSubsequenceLength+=2*rightHalfClosingUnbalanced;
            tree[treeNodeIndex].numOpeningUnbalanced=rightHalfOpeningUnbalanced+(leftHalfOpeningUnbalanced-rightHalfClosingUnbalanced);
            tree[treeNodeIndex].numClosingUnbalanced=leftHalfClosingUnbalanced;
        }
        else{
            tree[treeNodeIndex].maxSubsequenceLength+=2*leftHalfOpeningUnbalanced;
            tree[treeNodeIndex].numOpeningUnbalanced=rightHalfOpeningUnbalanced;
            tree[treeNodeIndex].numClosingUnbalanced=leftHalfClosingUnbalanced+(rightHalfClosingUnbalanced-leftHalfOpeningUnbalanced);
        }
    }
    public int query(int l,int r)
    {
        Triplet ans=queryHelper(1,0,n-1,l,r);
        return ans.maxSubsequenceLength;
    }
    private Triplet queryHelper(int treeNodeIndex,int nodeStart,int nodeEnd,int queryStart,int queryEnd)
    {
        if(queryEnd<nodeStart || queryStart>nodeEnd)
        {
            // no overlap
            Triplet ans=new Triplet();
            ans.maxSubsequenceLength=0;
            ans.numOpeningUnbalanced=0;
            ans.numClosingUnbalanced=0;
            return ans;
        }
        if(nodeStart>=queryStart && nodeEnd<=queryEnd)
        {
            // complete overlap
            return tree[treeNodeIndex];
        }
        // partial overlap
        int mid=(nodeStart+nodeEnd)/2;
        Triplet leftAns=queryHelper(treeNodeIndex*2,nodeStart,mid,queryStart,queryEnd);
        Triplet rightAns=queryHelper(treeNodeIndex*2+1,mid+1,nodeEnd,queryStart,queryEnd);
        
        Triplet ans=new Triplet();
        ans.maxSubsequenceLength=leftAns.maxSubsequenceLength+rightAns.maxSubsequenceLength;
        int leftHalfOpeningUnbalanced=leftAns.numOpeningUnbalanced;
        int rightHalfOpeningUnbalanced=rightAns.numOpeningUnbalanced;
        
        int leftHalfClosingUnbalanced=leftAns.numClosingUnbalanced;
        int rightHalfClosingUnbalanced=rightAns.numClosingUnbalanced;
        
        if(leftHalfOpeningUnbalanced>rightHalfClosingUnbalanced)
        {
            ans.maxSubsequenceLength+=2*rightHalfClosingUnbalanced;
            ans.numOpeningUnbalanced=rightHalfOpeningUnbalanced+(leftHalfOpeningUnbalanced-rightHalfClosingUnbalanced);
            ans.numClosingUnbalanced=leftHalfClosingUnbalanced;
        }
        else{
            ans.maxSubsequenceLength+=2*leftHalfOpeningUnbalanced;
            ans.numOpeningUnbalanced=rightHalfOpeningUnbalanced;
            ans.numClosingUnbalanced=leftHalfClosingUnbalanced+(rightHalfClosingUnbalanced-leftHalfOpeningUnbalanced);
        }
        return ans;
    }
}

class Triplet
{
    int maxSubsequenceLength;
    int numOpeningUnbalanced;
    int numClosingUnbalanced;
}