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.*;
import java.util.*;
import java.math.*;
import static java.lang.Math.*;
import static java.lang.Integer.parseInt;
import static java.lang.Long.parseLong;
import static java.lang.Double.parseDouble;
import static java.lang.String.*;

public class Main {

    static int [] segLen,open,close;
    static int x;
    
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
                                            //(new FileReader("input.in"));
        StringBuilder out = new StringBuilder();
        StringTokenizer tk;
        
        String s = in.readLine();
        segLen = new int[4*s.length()];
        open = new int[segLen.length];
        close = new int[segLen.length];
        
        for(int i=0; i<s.length(); i++) 
            insert(1,0,s.length()-1,i,s.charAt(i));
        
        int q = parseInt(in.readLine());
        while(q-- > 0) {
            tk = new StringTokenizer(in.readLine());
            int l = parseInt(tk.nextToken())-1,r = parseInt(tk.nextToken())-1;
            
            x = 0;
            out.append(findMax(1,0,s.length()-1,l,r)).append("\n");
        }
        
        System.out.print(out);
    }
    
    static void insert(int p,int l,int r,int i,char v) {
        if(l==r) {
            segLen[p] = 0;
            if(v=='(') open[p] = 1;
            else close[p] = 1;
            return;
        }
        
        if(i <= (l+r)/2)
            insert(2*p,l,(l+r)/2,i,v);
        else insert(2*p+1,(l+r)/2+1,r,i,v);
        
        segLen[p] = segLen[2*p]+segLen[2*p+1]+2*min(open[2*p],close[2*p+1]);
        open[p] = open[2*p+1]+(open[2*p]-min(open[2*p],close[2*p+1]));
        close[p] = close[2*p]+(close[2*p+1]-min(open[2*p],close[2*p+1]));
    }
    
    static int findMax(int p,int l,int r,int a,int b) {
        if(l>=a && r<=b) {
            int v = 0;
            if(x>0) 
                v = 2*min(x,close[p]);
            x = x+open[p]-min(x,close[p]);
            return segLen[p]+v;
        }
        
        if(r<a || l>b) return 0;
        
        return findMax(2*p,l,(l+r)/2,a,b)+findMax(2*p+1,(l+r)/2+1,r,a,b);
    }
}
