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 «()(())(())».
//package codechef;

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
 
public class Main {
	InputStream is;
	PrintWriter out;
	String INPUT = "";
	int[] seg;
	int[] star;
	int[] enar;
	long stock;
	String s;
	
	Main(int sz)
	{
		stock=0;
		seg=new int[4*sz];
		star=new int[4*sz];
		enar=new int[4*sz];
	}
	
	void buildtree(int n,int l,int r)
	{
		if (l==r)
		{
			if (s.charAt(l)=='(')
			{
				seg[n]=0;
				star[n]=1;
				enar[n]=0;
			}
			else
			{
				seg[n]=0;
				star[n]=0;
				enar[n]=1;
			}
		}
		else
		{
			int mid=(l+r)/2;
			buildtree(2*n+1,l,mid);
			buildtree(2*n+2,mid+1,r);
			int tb=Math.min(star[2*n+1], enar[2*n+2]);
			star[n]=star[2*n+1]+star[2*n+2]-tb;
			enar[n]=enar[2*n+1]+enar[2*n+2]-tb;
			seg[n]=seg[2*n+1]+seg[2*n+2]+2*tb;
		}
	}
	
	long query(int n,int l,int r,int x,int y)
	{
		if (x>r || y<l)
			return 0;
		else if (x<=l && r<=y)
		{
			long temp=Math.min(enar[n], stock);
			stock+=star[n];
			stock-=temp;
			return seg[n]+2*temp;
		}
		else
		{
			int mid=(l+r)/2;
			return query(2*n+1,l,mid,x,y)+query(2*n+2,mid+1,r,x,y);
		}
	}
	
	void solve()
	{
		s=ns();
		Main obj=new Main(s.length());
		obj.s=s;
		obj.buildtree(0, 0, s.length()-1);
//		System.out.println(obj.s);
//		System.out.println(Arrays.toString(obj.seg));
//		System.out.println(Arrays.toString(obj.star));
//		System.out.println(Arrays.toString(obj.enar));
		int m=ni();
		for(int i=0;i<m;i++)
		{
			int l=ni();
			int r=ni();
			obj.stock=0;
			out.println(obj.query(0, 0, s.length()-1, l-1, r-1));
		}
	}
	
	void run() throws Exception
	{
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
	}
	
	public static void main(String[] args) throws Exception { new Main(0).run(); }
	
	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;
	
	private int readByte()
	{
		if(lenbuf == -1)throw new InputMismatchException();
		if(ptrbuf >= lenbuf){
			ptrbuf = 0;
			try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
			if(lenbuf <= 0)return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
	private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
		
	private String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	
	private int ni()
	{
		int num = 0, b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	


	private void tr(Object... o) { if(INPUT.length() > 0)System.out.println(Arrays.deepToString(o)); }
}