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 javax.swing.text.Segment;
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[]args) throws IOException {
        Scanner sc = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        StringBuilder sb = new StringBuilder();
        char [] arr = sc.next().toCharArray();
        SegmentTree segmentTree = new SegmentTree (arr);
        int Q = sc.nextInt();
        while(Q -- > 0)
            out.print(segmentTree.query(sc.nextInt() -1  , sc.nextInt() - 1) + "\n");
        out.flush();
        out.close();
    }

    static class Node {
        int opened_not_closed , closed_not_opened , score;
        Node (int o , int c , int s) {opened_not_closed = o ; closed_not_opened = c; score = s;}
    }
    static class SegmentTree {
        char arr [];
        Node Tree [] ;
        int N;
        SegmentTree(char A[])
        {
            arr = A;
            N = A .length;
            Tree = new Node[(N << 1) << 1];
            build(1,0,N-1);
        }
        void build (int node , int left , int right)
        {
            if(left == right)
                Tree[node] = new Node(arr[left] == '('? 1 : 0 , arr[left] == ')' ? 1 : 0 , 0);
            else
            {
                int mid = mid(left , right) ;
                build(left(node) , left , mid);
                build(right(node) , mid + 1 , right);

                Node leftNode = Tree[left(node)] , rightNode = Tree[right(node)];

                // initially
                int score = Math.min(leftNode.opened_not_closed , rightNode.closed_not_opened) , opened_not_closed = leftNode.opened_not_closed + rightNode.opened_not_closed , closed_not_opened = leftNode.closed_not_opened + rightNode.closed_not_opened;
                opened_not_closed -= Math.min(leftNode.opened_not_closed , rightNode.closed_not_opened);
                closed_not_opened -= Math.min(leftNode.opened_not_closed , rightNode.closed_not_opened);

                Tree[node] = new Node (opened_not_closed , closed_not_opened , 2 * score + leftNode.score + rightNode .score);
            }
        }

        int  query (int l , int r) {return query(1 , 0 , N-1 ,  l , r).score;}
        Node query (int node , int curS , int curE , int l , int r)
        {
            if(curS >= l && curE<=r)
                return Tree[node];
            if(curS > r || curE < l)
                return new Node (0 , 0 , 0);

            Node leftNode = query(left(node) , curS , mid(curE , curS) , l , r) , rightNode = query(right(node) , mid(curS , curE) + 1 , curE , l ,  r);

            int score = Math.min(leftNode.opened_not_closed , rightNode.closed_not_opened) , opened_not_closed = leftNode.opened_not_closed + rightNode.opened_not_closed , closed_not_opened = leftNode.closed_not_opened + rightNode.closed_not_opened;
            opened_not_closed -= Math.min(leftNode.opened_not_closed , rightNode.closed_not_opened);
            closed_not_opened -= Math.min(leftNode.opened_not_closed , rightNode.closed_not_opened);

            return new Node (opened_not_closed , closed_not_opened , 2 * score + leftNode.score + rightNode .score);
        }
        int left (int pos) {return pos << 1;}
        int right (int pos) {return  (pos << 1) + 1;}
        int mid (int l , int r) {return  (l + r) >> 1 ;}
    }















    static  class Scanner
    {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

        public String next() throws IOException
        {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException {return Integer.parseInt(next());}

        public long nextLong() throws IOException {return Long.parseLong(next());}

        public String nextLine() throws IOException {return br.readLine();}

        public double nextDouble() throws IOException
        {
            String x = next();
            StringBuilder sb = new StringBuilder("0");
            double res = 0, f = 1;
            boolean dec = false, neg = false;
            int start = 0;
            if(x.charAt(0) == '-')
            {
                neg = true;
                start++;
            }
            for(int i = start; i < x.length(); i++)
                if(x.charAt(i) == '.')
                {
                    res = Long.parseLong(sb.toString());
                    sb = new StringBuilder("0");
                    dec = true;
                }
                else
                {
                    sb.append(x.charAt(i));
                    if(dec)
                        f *= 10;
                }
            res += Long.parseLong(sb.toString()) / f;
            return res * (neg?-1:1);
        }

        public boolean ready() throws IOException {return br.ready();}


    }

}