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.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;

public class C384{

	private byte[] inbarr = new byte[1024];
	private int lenbuf = 0, bufptr = 0;
	InputStream is;
	PrintWriter out;
	
	void solve()
	{
		char[] s = ns().toCharArray();
		SegmentTree st = new SegmentTree(s);
		for(int Q=ni();Q>0;Q--)
		{
			int l = ni() - 1, r = ni() - 1;
			out.println(st.query(l, r)[2]<<1);
		}
	}

	public class SegmentTree {
		
		public int B, S, N;
		public int[][] tree;
		public final int[] DEF = new int[3]; 
		
		SegmentTree(char[] a)
		{
			N = a.length;
			for(S = 1;S < N;S <<= 1);
			S <<= 1;
			tree = new int[S][3];
			B = S>>1;
			for(int i=0;i<N;i++) 
			{
				tree[B+i][0] = (a[i] == '(' ? 1 : 0);
				tree[B+i][1] = 1 - tree[B+i][0];
			}
			for(int i=B-1;i>0;i--) propagate(i);
		}
		
		public int[] query(int l, int r)
		{ 
			if (l > r) 
				return DEF;
			return query(1, l, r, 0, B-1);
		}
		
		private int[] query(int x, int l, int r, int curL, int curR)
		{
			if(curL > r || curR < l)
				return DEF;
			if(l <= curL && curR <= r)
				return tree[x];
			int mid = (curL + curR + 1)/2;
			int left[]  = query(x<<1, l, r, curL, mid-1);
			int right[] = query(x<<1|1, l, r, mid, curR);
			int[] ans = new int[3];
			int min = Math.min(left[0], right[1]);
			ans[2] = left[2] + right[2] + min;
			ans[0] = left[0] + right[0] - min;
			ans[1] = left[1] + right[1] - min;
			return ans;
		}
		
		void propagate(int x)
		{ 
			int min = Math.min(tree[x<<1][0], tree[x<<1|1][1]);
			tree[x][2] = tree[x<<1][2] + tree[x<<1|1][2] + min;
			tree[x][0] = tree[x<<1][0] + tree[x<<1|1][0] - min;
			tree[x][1] = tree[x<<1][1] + tree[x<<1|1][1] - min; 
		}
		
	}

	
	public static void main(String[] args){new C384();}
	
	public C384()
	{
		is = System.in;
		out = new PrintWriter(System.out);
		solve();
		out.flush();
	}
	
	int readByte()
	{
		if(lenbuf==-1)
			throw new InputMismatchException();
		if(bufptr>=lenbuf)
		{
			bufptr = 0;
			try {
				lenbuf = is.read(inbarr);
			} catch(Exception e) { 
				throw new InputMismatchException();
			}
			if(lenbuf<=0)
				return -1;
		}
		return inbarr[bufptr++];
	}
	
	boolean isSpaceChar(int x) {return (x<33 || x>126);}	
	char nc() { return (char)skip();}
	
	int skip()
	{
		int x;
		while((x=readByte())!=-1 && isSpaceChar(x));
		return x;
	}
	
	int ni()
	{
		int ret = 0;
		boolean minus = false;
		int x = skip();
		if(x=='-') 
		{
			minus = true;
			x = readByte();
		}
		while(!isSpaceChar(x))
		{
			ret = ret*10 + x -'0';
			x = readByte();
		}
		return minus ? -ret:ret;
	}
	
	long nl()
	{
		long ret = 0;
		boolean minus = false;
		int x = skip();
		if(x=='-') 
		{
			minus = true;
			x = readByte();
		}
		while(!isSpaceChar(x))
		{
			ret = ret*10 + x -'0';
			x = readByte();
		}
		return minus ? -ret:ret;
	}
	
	String ns()
	{
		StringBuilder sb = new StringBuilder();
		int x = skip();
		while(!isSpaceChar(x))
		{
			sb.appendCodePoint(x);
			x = readByte();
		}
		return sb.toString();
	}
	
	int[] na(int n)
	{
		int[] ret = new int[n];
		for(int i=0;i<n;i++)
			ret[i] = ni();
		return ret;
	}
	
}
