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 CF;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;


public class D {
    static class Pair {
	int open;
	int close;
	int ans;
	public Pair(int a,int b, int c){
	    open = a;
	    close = b;
	    ans = c;
	}
	public String toString(){
	    return open + " " + close + " " + ans;
	}
    }
    public static void main(String[] args) throws IOException   {
	Scanner bf = new Scanner(System.in);
	PrintWriter out = new PrintWriter(System.out);
	String s = bf.nextLine();
	int n = s.length();
	int q = bf.nextInt();
	int N = 1; while(N < n) N <<= 1; 
	int[] in = new int[N + 1];
	for(int i = 1; i <= n; i++)
	    in[i] = s.charAt(i-1) == '('?0:1;

	SegmentTree sg = new SegmentTree(in);
//	out.println(Arrays.toString(sg.sTree));
	for (int i = 0; i < q; i++)
	{
	    out.println(sg.query(bf.nextInt(), bf.nextInt()).ans);
	}
	out.flush();
	out.close();
    }
    static class Scanner 
    {
	StringTokenizer st;
	BufferedReader br;

	public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

	public String next() throws IOException 
	{
	    while (st == null || !st.hasMoreTokens()) 
		st = new StringTokenizer(br.readLine());
	    return st.nextToken();
	}

	public int nextInt() throws IOException {return Integer.parseInt(next());}

	public long nextLong() throws IOException {return Long.parseLong(next());}

	public String nextLine() throws IOException {return br.readLine();}

	public double nextDouble() throws IOException
	{
	    String x = next();
	    StringBuilder sb = new StringBuilder("0");
	    double res = 0, f = 1;
	    boolean dec = false, neg = false;
	    int start = 0;
	    if(x.charAt(0) == '-')
	    {
		neg = true;
		start++;
	    }
	    for(int i = start; i < x.length(); i++)
		if(x.charAt(i) == '.')
		{
		    res = Long.parseLong(sb.toString());
		    sb = new StringBuilder("0");
		    dec = true;
		}
		else
		{
		    sb.append(x.charAt(i));
		    if(dec)
			f *= 10;
		}
	    res += Long.parseLong(sb.toString()) / f;
	    return res * (neg?-1:1);
	}

	public boolean ready() throws IOException {return br.ready();}
    }
    static class SegmentTree {		

	int N; 			
	int[] array;
	Pair [] sTree;

	SegmentTree(int[] in)		
	{
	    array = in; N = in.length - 1;
	    sTree = new Pair[N<<1];		
	    build(1,1,N);
	}

	void build(int node, int b, int e)	
	{
	    if(b == e)					
		sTree[node] = new Pair(array[b]==0?1:0,array[b]==1?1:0,0);
	    else						
	    {
		build(node<<1,b,(b+e)/2);
		build((node<<1)+1,(b+e)/2+1,e);
		Pair q1 = sTree[node<<1];
		Pair q2 = sTree[(node<<1)+1];
		int min = Math.min(q1.open, q2.close);
		sTree[node] = new Pair(q1.open+q2.open-min,q1.close+q2.close-min,q1.ans+q2.ans+min*2);
	    }
	}

	Pair query(int i, int j)
	{
	    return query(1,1,N,i,j);
	}

	Pair query(int node, int b, int e, int i, int j)	
	{
	    if(i>e || j <b){
		return new Pair(0,0,0);		
	    }
	    if(b>= i && e <= j)
		return sTree[node];
	    Pair q1 = query(node<<1,b,(b+e)/2,i,j);
	    Pair q2 = query((node<<1)+1,(b+e)/2+1,e,i,j);
	    int min = Math.min(q1.open, q2.close);
	    return new Pair(q1.open+q2.open-min,q1.close+q2.close-min,q1.ans+q2.ans+min*2);
	}

    }
}
