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.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.TreeMap;
						public class Main implements Runnable
						{
							static final long MOD = 1000000007L;
							static final long MOD2 = 1000000009L;
							static class InputReader
							{
								private InputStream stream;
								private byte[] buf = new byte[1024];
								private int curChar;
								private int numChars;
								private SpaceCharFilter filter;
								private BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
						 
								public InputReader(InputStream stream)
								{
									this.stream = stream;
								}
								
								public int read()
								{
									if (numChars==-1) 
										throw new InputMismatchException();
									
									if (curChar >= numChars)
									{
										curChar = 0;
										try 
										{
											numChars = stream.read(buf);
										}
										catch (IOException e)
										{
											throw new InputMismatchException();
										}
										
										if(numChars <= 0)				
											return -1;
									}
									return buf[curChar++];
								}
							 
								public String nextLine()
								{
									String str = "";
						            try
						            {
						                str = br.readLine();
						            }
						            catch (IOException e)
						            {
						                e.printStackTrace();
						            }
						            return str;
								}
								public int nextInt()
								{
									int c = read();
									
									while(isSpaceChar(c)) 
										c = read();
									
									int sgn = 1;
									
									if (c == '-') 
									{
										sgn = -1;
										c = read();
									}
									
									int res = 0;
									do 
									{
										if(c<'0'||c>'9') 
											throw new InputMismatchException();
										res *= 10;
										res += c - '0';
										c = read();
									}
									while (!isSpaceChar(c)); 
									
									return res * sgn;
								}
								
								public long nextLong() 
								{
									int c = read();
									while (isSpaceChar(c))
										c = read();
									int sgn = 1;
									if (c == '-') 
									{
										sgn = -1;
										c = read();
									}
									long res = 0;
									
									do 
									{
										if (c < '0' || c > '9')
											throw new InputMismatchException();
										res *= 10;
										res += c - '0';
										c = read();
									}
									while (!isSpaceChar(c));
										return res * sgn;
								}
								
								public double nextDouble() 
								{
									int c = read();
									while (isSpaceChar(c))
										c = read();
									int sgn = 1;
									if (c == '-') 
									{
										sgn = -1;
										c = read();
									}
									double res = 0;
									while (!isSpaceChar(c) && c != '.') 
									{
										if (c == 'e' || c == 'E')
											return res * Math.pow(10, nextInt());
										if (c < '0' || c > '9')
											throw new InputMismatchException();
										res *= 10;
										res += c - '0';
										c = read();
									}
									if (c == '.') 
									{
										c = read();
										double m = 1;
										while (!isSpaceChar(c)) 
										{
											if (c == 'e' || c == 'E')
												return res * Math.pow(10, nextInt());
											if (c < '0' || c > '9')
												throw new InputMismatchException();
											m /= 10;
											res += (c - '0') * m;
											c = read();
										}
									}
									return res * sgn;
								}
								
								public String readString() 
								{
									int c = read();
									while (isSpaceChar(c))
										c = read();
									StringBuilder res = new StringBuilder();
									do 
									{
										res.appendCodePoint(c);
										c = read();
									} 
									while (!isSpaceChar(c));
									
									return res.toString();
								}
							 
								public boolean isSpaceChar(int c) 
								{
									if (filter != null)
										return filter.isSpaceChar(c);
									return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
								}
							 
								public String next() 
								{
									return readString();
								}
								
								public interface SpaceCharFilter 
								{
									public boolean isSpaceChar(int ch);
								}
							}
						 	
							public static void main(String args[]) throws Exception
							{
								new Thread(null, new Main(),"Main",1<<26).start();
							}
							int MAXN = 1000001;
							ArrayList<Integer> adj[];

							
							int[] dx = {1,-1,0,0};
							int[] dy = {0,0,1,-1};
							public void run() 
							{
								try {
									//InputReader sc= new InputReader(new FileInputStream("input.txt"));
									//PrintWriter w= new PrintWriter(new FileWriter("output.txt"));
									InputReader sc = new InputReader(System.in);
                                    PrintWriter w = new PrintWriter(System.out);
									String s=  sc.next();
									segTree = new Node[4*s.length()];
									build(0, s.length()-1, 0, s);
									int q = sc.nextInt();
									while(q-- > 0) {
										int a = sc.nextInt()-1;
										int b = sc.nextInt()-1;
										w.println(2*query(0, s.length()-1, 0, a, b).max);
									}
									w.close();							
								}
								catch(Exception e) {
									System.out.println(e);
								}
							}
							static class Node{
								int left;
								int right;
								int max;
								Node(){
									left = 0;
									right = 0;
									max = 0;
								}
							}
							Node[] segTree;
							void build(int l,int r,int pos,String s) {
								if(l == r) {
									segTree[pos] = new Node();
									if(s.charAt(l) == '(') {
										segTree[pos].right = 1;
									}else {
										segTree[pos].left = 1;
									}
									return;
								}
								int mid = (l + r)/2;
								build(l, mid, 2*pos+1, s);
								build(mid+1, r, 2*pos+2, s);
								segTree[pos] = merge(segTree[2*pos+1],segTree[2*pos+2]);
							}
							Node merge(Node n1,Node n2) {
								Node navi = new Node();
								navi.max = n1.max + n2.max + Math.min(n1.right,n2.left);
								navi.left = n1.left + n2.left - Math.min(n1.right,n2.left);
								navi.right = n2.right + n1.right -  Math.min(n1.right,n2.left);
								return navi;
							}
							Node query(int l,int r,int pos,int start,int end) {
								if(l > r || l > end || r < start) {
									return new Node();
								}
								if(l >= start && r <= end) {
									return segTree[pos];
								}
								int mid = (l + r)/2;
								Node p1 = query(l, mid, 2*pos+1, start, end);
								Node p2 = query(mid+1, r, 2*pos+2, start, end);
								return merge(p1,p2);
							}
							static class Pair implements Comparable<Pair>{
								int a;
								int b;
								
								Pair(int a,int b){
									this.a = a;
									this.b = b;
								
								}
								@Override
								public int compareTo(Pair o) {
									// TODO Auto-generated method stub
									return Long.compare(this.b,o.b);
								}
								public boolean equals(Object o) {
									Pair p = (Pair)o;
									return this.a == p.a && this.b == p.b;
								}
								public int hashCode(){
									return Long.hashCode(a)*27 + Long.hashCode(b)* 31;
								}
							}
							
						}