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 static java.lang.Math.*;
import static java.lang.System.currentTimeMillis;
import static java.lang.System.exit;
import static java.lang.System.arraycopy;
import static java.util.Arrays.sort;
import static java.util.Arrays.binarySearch;
import static java.util.Arrays.fill;

import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        try {
            if (new File("input.txt").exists())
                System.setIn(new FileInputStream("input.txt"));
        } catch (SecurityException e) {
        }
        new Main().run();
    }

    BufferedReader in;
    PrintWriter out;
    StringTokenizer st = new StringTokenizer("");

    private void run() throws IOException {
        in = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        solve();
        in.close();
        out.close();
    }
    
    final int MAXN = 1000011;
    int[] t = new int[4 * MAXN];
    void buildT1(int v, int l, int r){
        if(l == r){
            t[v] = 0;
        } else {
            int m = (l + r) >> 1;
            buildT1(v << 1, l, m);
            buildT1((v << 1) + 1, m+1 ,r);
            t[v] = t[v << 1] + t[(v << 1) + 1] + 
                    2 * min(cntOpen(l + 1,m + 1) - t[v << 1]/2, 
                            cntClose(m + 2,r + 1) - t[(v << 1) + 1]/2);
        }
    }
    int maxLen(int v, int l, int r, int ll, int rr){
        if( l == r || ll > rr )
            return 0;
        if(l == ll && r == rr){
            return t[v];
        } else {
            int m = (l+r) >> 1;
            int left = maxLen(v << 1, l, m, ll, min(rr,m));
            int right = maxLen((v << 1) + 1, m + 1, r, max(m + 1,ll),rr);
            return left + right + 2 * min(cntOpen(max(l + 1, ll + 1),min(m + 1, rr + 1)) - left / 2, 
                    cntClose(max(m + 2,ll+1),min(r + 1,rr + 1)) - right / 2);
        }
    }
    int[] preOpen;
    void initOpen(){
        preOpen = new int[s.length + 1];
        for(int i = 0; i < s.length; i++)
            preOpen[i+1] = preOpen[i] + ((s[i] == '(') ? 1 : 0);
    }
    int cntOpen(int l, int r){
        r = min(r,s.length);
        if(l > s.length || l > r)
            return 0;
        return preOpen[r] - preOpen[l-1];
    }
    int cntClose(int l, int r){
        r = min(r,s.length);
        if(l > s.length || l > r)
            return 0;
        return r - l + 1 - cntOpen(l,r);
    }
    char []s;
    
    private void solve() throws IOException {
        s = nextToken().toCharArray();
        initOpen();
        int lenT1 = 0;
        while((1 << lenT1) < s.length) lenT1++;
        lenT1 = 1 << lenT1;
        buildT1(1,0,lenT1-1);
        int q = nextInt();
        for(int i = 0; i < q; i++)
            out.println(maxLen(1,0,lenT1-1,nextInt()-1, nextInt()-1));
    }
    
    int gcd(int a, int b){return b == 0 ? a : gcd(b,a%b);}
    
    void arrayToString(int[] m){
        Arrays.toString(m);
    }
    
    String nextToken() throws IOException {
        while (!st.hasMoreTokens())
            st = new StringTokenizer(in.readLine());
        return st.nextToken();
    }
    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }
    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }
    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
    String nextLine() throws IOException {
        st = new StringTokenizer("");
        return in.readLine();
    }
    boolean EOF() throws IOException {
        while (!st.hasMoreTokens()) {
            String s = in.readLine();
            if (s == null)
                return true;
            st = new StringTokenizer(s);
        }
        return false;
    }
}
