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.*;
import java.math.*;


public class Main
{
    private static char[] array;
    private static int[] tree;
    private static int[] left;
    private static int[] right;
    // private static int[] lazy;

    //build function
    private static void build(int node,int start,int end){
        if(start == end){
            if(array[start] == '(')
                left[node] = 1;
            else
                right[node] = 1;
        }
        else{
            int mid = start + (end - start)/2;
            build(2*node,start,mid);
            build(2*node+1,mid+1,end);
            
            int temp = Math.min(left[2*node],right[2*node+1]);
            tree[node] = tree[2*node] + tree[2*node+1] + temp;
            left[node] = left[2*node] + left[2*node + 1] - temp;
            right[node] = right[2*node] + right[2*node + 1] - temp;
        }
    }

    private static Node queryRange(int node, int start, int end, int l, int r){
        if((start > end) || (start > r) || (end < l))
            return new Node(0,0,0);//operation can be changed here

        if(start>=l && end <=r)
            return new Node(tree[node],left[node],right[node]);

        int mid = start + (end - start)/2;
        Node p1 = queryRange(node * 2, start, mid, l, r);
        Node p2 = queryRange(node * 2 + 1, mid + 1, end, l, r);
        
        int temp = Math.min(p1.left,p2.right);
        return new Node(p1.correct + p2.correct + temp,p1.left + p2.left - temp,p1.right + p2.right - temp);
    }
    
    private static int log2(int n){
    if(n <= 0) throw new IllegalArgumentException();
    return 31 - Integer.numberOfLeadingZeros(n);
    }

    public static void main (String[] args) throws IOException
    {
        // Scanner sc = new Scanner(System.in);
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        char[] tt = reader.readLine().toCharArray();
        array = new char[tt.length+1];
        for(int i = 1; i <= tt.length; i++){
            array[i] = tt[i-1];
        }
        int length = 1 << (log2(tt.length) + 2);
        tree = new int[length];
        left = new int[length];
        right = new int[length];
        build(1,1,tt.length);
        int M = Integer.parseInt(reader.readLine());
        for(int i = 1; i <= M; i++){
            String[] nums = reader.readLine().split(" ");
            int l = Integer.parseInt(nums[0]);
            int r = Integer.parseInt(nums[1]);
            System.out.println(2*queryRange(1,1,tt.length,l,r).correct);
        }
    }
    static class Node{
    int correct;
    int left;
    int right;
    public Node(int a, int b, int c){
        correct = a;
        left = b;
        right = c;
    }
}
}