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.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
    static char[] arr;
    static int[] segment;
    static int[] left;
    static int[] right;

    public static void build(int v,int l,int r){
        if(l+1==r) {
            if(arr[l]=='(')
                left[v] = 1;
            else
                right[v] = 1;
        }
        else{
            int mid;
            mid = (l+r)/2;
            build(2*v,l,mid);
            build(2*v+1,mid,r);
            int x = Math.min(left[2*v],right[2*v+1]);
            segment[v] = segment[2*v] + segment[2*v+1]+ x*2;
            left[v] = left[2*v] + left[2*v+1] -x;
            right[v] = right[2*v] + right[2*v+1] - x;
        }
    }

    public static int[] query(int x,int y,int i,int l,int r){
        if(l>=y || x>=r)
            return new int[]{0,0,0};
        if(x<=l && r<=y)
            return new int[]{segment[i],left[i],right[i]};
        int mid = (l+r)/2;
        int[] v1 = query(x,y,2*i,l,mid);
        int[] v2 = query(x,y,2*i+1,mid,r);
        int v = Math.min(v1[1],v2[2]);
        int s =v1[0] +v2[0]+ v*2;
        int left = v1[1]+v2[1]-v;
        int right = v1[2]+v2[2]-v;
        return new int[]{s,left,right};
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in  = new BufferedReader(new InputStreamReader(System.in));
        arr = in.readLine().toCharArray();
        segment = new int[arr.length*4];
        left = new int[arr.length*4];
        right = new int[arr.length*4];
        build(1,0,arr.length);
        int q = Integer.parseInt(in.readLine());
        for(int i=0;i<q;i++){
            String[] input = in.readLine().split(" ");
            int l = Integer.parseInt(input[0]) -1;
            int r =Integer.parseInt(input[1]);
            System.out.println(query(l,r,1,0,arr.length)[0]);
        }
    }
}