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.*;

public class C {










    static boolean tests = false;
    static class SegmentTree{
        int n;
        Node[] tree;
        char[] s;
        SegmentTree(String s){
            this.n = s.length();
            this.s = new char[n+1];
            this.s[0] = 'x';
            for (int i = 1; i <= n; ++i){
                this.s[i] = s.charAt(i-1);
            }
            this.tree = new Node[4*n+5];
            build(1, 1, n);
        }
        int l(int u){return 2*u;}
        int r(int u){return l(u)+1;}
        Node merge(Node l, Node r){
            if (l == null) return r;
            if (r == null) return l;
            Node x = new Node(l.left, r.right);
            x.open = l.open+r.open;
            x.close = l.close+r.close;
            int open = l.open-(l.matches/2);
            int close = r.close-(r.matches/2);
            x.matches = l.matches+r.matches;
            x.matches += 2*Math.min(open, close);
            return x;
        }
        void build(int u, int left, int right){
            tree[u] = new Node(left, right);
            if (left == right){
                if (s[left] == ')') ++tree[u].close;
                else ++tree[u].open;
                return;
            }
            int mid = (left+right)/2;
            build(l(u), left, mid);
            build(r(u), mid+1, right);
            tree[u] = merge(tree[l(u)], tree[r(u)]);
        }
        int rangeSeq(int left, int right){
            return rangeSeq(1, left, right).matches;
        }
        Node rangeSeq(int u, int left, int right){
            if (tree[u].left > right || left > tree[u].right) return null;
            if (left <= tree[u].left && tree[u].right <= right) return tree[u];
            return merge(rangeSeq(l(u), left, right), rangeSeq(r(u), left, right));
        }

        static class Node{
            int open, close, matches, left, right;
            Node(int left, int right){
                this.left = left;
                this.right = right;
                this.open = 0;
                this.close = 0;
                this.matches = 0;
            }
        }
    }
    static void solve(){
        String s = fs.next();
        SegmentTree string = new SegmentTree(s);
        int q = fs.nextInt();
        while (q-- > 0) out.println(string.rangeSeq(fs.nextInt(), fs.nextInt()));
    }



















    static FastScanner fs;
    static PrintWriter out;
    static int int_max = (int)1e9, mod = int_max+7;
    public static void main(String[] args) {
        fs = new FastScanner();
        out = new PrintWriter(System.out);
        int t;
        if (tests) t = fs.nextInt();
        else t = 1;
        while (t-- > 0) solve();
        out.close();
    }
    static class FastScanner {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer("");
        String next() {
            while (!st.hasMoreTokens())
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
        int[] readIntArray(int n) {
            int[] a=new int[n];
            for (int i=0; i<n; i++) a[i]=nextInt();
            return a;
        }
        long[] readLongArray(int n){
            long a[] = new long[n];
            for (int i = 0; i < n; ++i){
                a[i] = nextLong();
            }
            return a;
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDouble(){
            return Double.parseDouble(next());
        }
    }
}