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.File;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Scanner;


public class Main {
	static ArrayList<Integer> toPrint;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		toPrint = new ArrayList<Integer>();
		String line  = br.readLine();
		SegTree s = new SegTree(line.toCharArray());
		int q =Integer.parseInt(br.readLine());
		while(q-->0)
		{
			String [] sp = br.readLine().split(" ");
			toPrint.add(s.find(Integer.parseInt(sp[0]), Integer.parseInt(sp[1])).pair);
		}
		for(int i=0;i<toPrint.size()-1;i++)
			bw.append(toPrint.get(i)+"\n");
		bw.append(toPrint.get(toPrint.size()-1)+"");
		bw.flush();
		bw.close();
	}
	static class SegTree{
		Node[] tree;
		char[] elements;
		int n;
		SegTree(char [] in)
		{
			elements = in;
			n= 1;
			while(n<in.length)
				n*=2;
			tree= new Node[n<<1];
			build(1,1,n);
		}
		void build(int node,int b,int e)
		{
			if(node>=tree.length || node<0 || b>elements.length)
				return;
			if(b==e)
			{
				tree[node]=new Node(elements[b-1]);
				return;
			}
			int mid= (b+e)/2;
			build(node<<1,b,mid);
			build(node<<1|1,mid+1,e);
			boolean isLeftNull = tree[node<<1]==null;
			boolean isRightNull = tree[node<<1|1]==null;
			int newely_Completed = Math.min(isLeftNull?0: tree[node<<1].opened,isRightNull? 0:tree[node<<1|1].closed);
			int opened =(isLeftNull? 0:tree[node<<1].opened)+(isRightNull?0:tree[node<<1|1].opened)-newely_Completed ; 
			int closed=(isLeftNull?0:tree[node<<1].closed)+(isRightNull? 0:tree[node<<1|1].closed)-newely_Completed ;
			int pair=(isLeftNull?0:tree[node<<1].pair)+(isRightNull?0:tree[node<<1|1].pair)+2*newely_Completed ;
			tree[node]= new Node(opened,closed,pair);
		}
		//note : index is one based
		/*void updatePoint(int index,int val)
		{
			int diff =val-elements[index]; 
			elements[index-1] = val;
			index+= n-1;
			tree[index]+=diff;
			while(index>1)
			{
				index>>=1; //index = index>>1; i.e : index = index/2
				tree[index] = tree[index<<1]+tree[index<<1|1];
			}
		}*/
		Node find(int l ,int r)
		{
			return find(1,1,n,l,r);
		}
		Node find(int treeIndex,int s,int e,int l , int r)
		{
			if(l>e || r <s || s>=elements.length)
				return new Node(0,0,0);
			if(l<=s && r>=e)
				return tree[treeIndex];
			if(s==e)
				return tree[treeIndex];
			int mid = s+e >>1;
			Node n1 =find(treeIndex<<1,s,mid,l, r);
			Node n2 = find(treeIndex<<1|1,mid+1,e,l,r);
			int newely_Completed = Math.min(n1.opened, n2.closed);
			int opened =n1.opened+n2.opened-newely_Completed ; 
			int closed=n1.closed+n2.closed-newely_Completed ;
			int pair=n1.pair+n2.pair+2*newely_Completed ;
			
			return new Node(opened,closed,pair);
		}
		
	}
	static class Node{
		int opened;
		int closed;
		int pair;
		Node(char c)
		{
			opened =0;
			closed=0;
			pair =0;
			if(c=='(')
				opened++;
			else if(c==')')
				closed++;
			
		}
		Node(int o,int c,int p)
		{
			this.opened =o;
			this.closed=c;
			this.pair = p;
		}
		public String toString()
		{
			return this.opened+" "+this.closed+" "+this.pair;
		}
	}
	
}