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.util.*;
import java.io.*;
public class C223 {
public static void main(String[] args) throws IOException
{
    input.init(System.in);
    s = input.next();
    int n = s.length();
    IT it = new IT(n);
    s = null;
    int m = input.nextInt();
    PrintWriter out = new PrintWriter(System.out);
    for(int i = 0; i<m; i++)
    {
        out.println(2*it.get(input.nextInt()-1, input.nextInt()-1)[0]);
    }
    out.close();
}
static String s;
//Minimum Interval Tree
static class IT
{
    int[] left,right, complete, open, close, a, b;
    IT(int n)
    {
        complete = new int[4*n];
        open = new int[4*n];
        close = new int[4*n];
        a = new int[4*n];
        b = new int[4*n];
        init(0,0, n-1);
    }
    int init(int at, int l, int r)
    {
        a[at] = l;
        b[at] = r;
        if(l==r)
        {
            //left[at] = right [at] = -1;
            if(s.charAt(l) == '(') open[at] = 1;
            else close[at] = 1;
        }
        else 
        {
            int mid = (l+r)/2;
            //left[at] = init(2*at+1,l,mid);
            //right[at] = init(2*at+2,mid+1,r);
            init(2*at+1,l,mid);
            init(2*at+2,mid+1,r);
            int left = 2*at+1;
            int right = 2*at+2;
            int o1 = open[left], o2 = open[right];
            int c1 = close[left], c2 = close[right];
            int merge = Math.min(o1, c2);
            complete[at] = complete[left] + complete[right] + merge;
            open[at] = o1 + o2 - merge;
            close[at] = c1 + c2 - merge;
            //System.out.println(a[at]+" "+b[at]+" "+complete[at]+" "+open[at]+" "+close[at]);
        }
        return at++;
    }
    //return the min over [x,y]
    int[] get(int x, int y)
    {
        return go(x,y, 0);
    }
//  void push(int at)
//  {
//      if(prop[at] != 0)
//      {
//          go3(a[left[at]], b[left[at]], prop[at], left[at]);
//          go3(a[right[at]], b[right[at]], prop[at], right[at]);
//          prop[at] = 0;
//      }
//  }
    int[] go(int x,int y, int at)
    {
        if(at==-1 || y<a[at] || x>b[at]) return new int[]{0, 0, 0};
        if(x <= a[at] && y>= b[at]) return new int[]{complete[at], open[at], close[at]};
        //push(at);
        int left = 2*at+1, right = 2*at+2;
        int[] l = go(x, y, left), r = go(x, y, right);
        int merge = Math.min(l[1], r[2]);
        return new int[]{r[0]+l[0]+merge, r[1]+l[1]-merge, r[2]+l[2]-merge};
    }
}
public static class input {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    /** call this method to initialize reader for InputStream */
    static void init(InputStream input) {
        reader = new BufferedReader(
                     new InputStreamReader(input) );
        tokenizer = new StringTokenizer("");
    }

    /** get next word */
    static String next() throws IOException {
        while ( ! tokenizer.hasMoreTokens() ) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(
                   reader.readLine() );
        }
        return tokenizer.nextToken();
    }

    static int nextInt() throws IOException {
        return Integer.parseInt( next() );
    }
    
    static double nextDouble() throws IOException {
        return Double.parseDouble( next() );
    }
    static long nextLong() throws IOException {
        return Long.parseLong( next() );
    }
}
}
