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

public class Solution {

     public static void main(String args[])throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer();
        String str = br.readLine().trim();
        char arr[] = str.toCharArray();
        int n = arr.length;
        Node tree[] = new Node[4*n+1];
        
        
        build(0,0,n-1,arr,tree);

        int q = Integer.parseInt(br.readLine());
        while(q>0){
            q--;
            String s[] = br.readLine().trim().split(" ");
            int l = Integer.parseInt(s[0]);
            int r = Integer.parseInt(s[1]);
            l--;
            r--;
            Node A = query(0,0,n-1,l,r,tree);
            sb.append(A.ans+"\n");
        }
        System.out.print(sb);

    }

    public static Node combine(Node a, Node b){

        Node n = new Node(0,0,0);
        int temp = (int)Math.min(a.open, b.close);
        n.ans = a.ans + b.ans + (2*temp);
        n.open = a.open+b.open-temp;
        n.close = a.close+b.close-temp;

        return n;
    }

    public static void build(int index, int start, int end, char arr[], Node tree[]){

        if(start == end){
            if(arr[start]== '(')
                tree[index] = new Node(0,1,0);
            else
                tree[index] = new Node(0,0,1);
        }
            
        else{

            int mid = start + (end-start)/2;
            build((2*index)+1, start, mid, arr, tree);
            build((2*index)+2, mid+1, end, arr, tree);

            tree[index] = combine(tree[2*index+1] , tree[2*index+2]);
        }

    }
    
    public static Node query(int index, int start, int end, int l, int r, Node tree[]){

        if(l>r)
            return new Node(0,0,0);
        else if(start==l && end==r)
            return tree[index];
        else{

            int mid = start + (end-start)/2;

            Node v1 = query(2*index+1, start, mid, l, (int)Math.min(r,mid), tree);
            Node v2 = query(2*index+2, mid+1, end, (int)Math.max(l,mid+1), r, tree);

            return combine(v1, v2);
        }

    }
    
}

class Node{

    int ans;
    int open;
    int close;

    Node(int a, int b, int c){
        ans = a;
        open = b;
        close = c;
    }

}
