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


public class P4{
    public static void main(String args[] ) throws Exception {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder("");
		String str="$"+br.readLine();
		int arr[]=new int[str.length()];
		for(int i=1;i<str.length();i++)
			if(str.charAt(i)=='(')
				arr[i]=1;
		//System.out.println(Arrays.toString(arr)+"Len"+arr.length);
		SegTree seg=new SegTree(arr,arr.length-1);
		int q=Integer.parseInt(br.readLine());
		while(q-->0){
			String ab[]=br.readLine().split(" ");
			int a=Integer.parseInt(ab[0]);
			int b=Integer.parseInt(ab[1]);
			if(a==b)
				sb.append("0").append("\n");
			else
				sb.append(""+2*seg.query(a,b)).append("\n");
		}
		System.out.println(sb.toString());
    }
}


class Node{
	int t;int o;int c;
	Node(int a,int b,int c){t=a;o=b;this.c=c;}
	public String toString(){
		return "("+this.t+","+this.o+","+this.c+")";
	}
}
class SegTree{
    Node tree[];
    int arr[];
    int N;
    SegTree(int ar[],int n){
        tree=new Node[5*n+1];
		for(int i=0;i<tree.length;i++) tree[i]=new Node(0,0,0);
        arr=ar.clone();
        N=n;
        build(1,1,N);          // 1-based indexing
    }
    private void build(int curnode,int start,int end){
        if(end==start){
            if(arr[start]==1)
				tree[curnode].o=1;
			else
				tree[curnode].c=1;
			//System.out.println(start+" "+end+" :("+tree[curnode].t+","+tree[curnode].o+","+tree[curnode].c+")");
			return;
		}
		int mid=(start+end)/2;
		build(2*curnode,start,mid);
		build(2*curnode+1,mid+1,end);
		int cur=Math.min(tree[2*curnode].o,tree[2*curnode+1].c);   //Range Minimum
		tree[curnode].t=tree[2*curnode].t+tree[2*curnode+1].t+cur;
		tree[curnode].o=tree[2*curnode].o+tree[2*curnode+1].o-cur;
		tree[curnode].c=tree[2*curnode].c+tree[2*curnode+1].c-cur;
		//System.out.println(start+" "+end+" :("+tree[curnode].t+","+tree[curnode].o+","+tree[curnode].c+")");
    }
	
    public int query(int left,int right){
        Node res= getMin(1,1,N,left,right);
		return res.t;
    }
     private Node getMin(int curnode,int start,int end,int left,int right){
        if(left>end || right<start){
			//System.out.println(start+":"+end+":OutOfRange");
            return new Node(0,0,0);
		}
        if(left<=start && right>=end){
			//System.out.println(start+":"+end+":"+tree[curnode]);
            return tree[curnode];
		}
        int mid=(start+end)/2;
        Node l=getMin(2*curnode,start,mid,left,right);
        Node r=getMin(2*curnode+1,mid+1,end,left,right);
        int cur=Math.min(l.o,r.c);
		int t=l.t+r.t+cur;
		int op=l.o+r.o-cur;
		int cl=l.c+r.c-cur;
		//System.out.println(t+" "+op+" "+cl);
		//Node nd=new Node(t,op,cl);
		//System.out.println(start+":"+end+"$"+l+" :"+r+": "+nd);
		return new Node(t,op,cl);
    }
}
