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 «()(())(())».
//package practice.E;

import java.io.*;
import java.util.*;

public class CF380C {

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);

        char[] s = sc.next().toCharArray();
        int n = s.length;
        int q = sc.nextInt();
        int[][] queries = new int[q][3];
        for (int i = 0; i < q; i++)
            queries[i] = new int[]{sc.nextInt(), sc.nextInt(), i};


        int N = 1; while(N < n) N <<= 1; //padding

        int[] in = new int[N + 1];
        SegmentTree t = new SegmentTree(in);

        Arrays.sort(queries, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                return b[0] - a[0];
            }
        });

        int[] ans = new int[q];

        int qi = 0;
        Stack<Integer> st = new Stack<>();
        for (int i = n-1; i >= 0; i--) {
            if(s[i] == ')'){
                st.add(i+1);
            }else{
                if(!st.isEmpty()){
                    int idx = st.pop();
                    t.update_range(idx, idx, 1);
                }
            }

            while(qi != q && queries[qi][0] == i+1){
                ans[queries[qi][2]] = t.query(queries[qi][0], queries[qi][1]);
                qi++;
            }
        }

        for (int i = 0; i < ans.length; i++) {
            pw.println(ans[i]*2);
        }
        pw.flush();
        pw.close();
    }

    static class SegmentTree {		// 1-based DS, OOP

        int N; 			//the number of elements in the array as a power of 2 (i.e. after padding)
        int[] array, sTree, lazy;

        SegmentTree(int[] in)
        {
            array = in; N = in.length - 1;
            sTree = new int[N<<1];		//no. of nodes = 2*N - 1, we add one to cross out index zero
            lazy = new int[N<<1];
            build(1,1,N);
        }

        void build(int node, int b, int e)	// O(n)
        {
            if(b == e)
                sTree[node] = array[b];
            else
            {
                int mid = b + e >> 1;
                build(node<<1,b,mid);
                build(node<<1|1,mid+1,e);
                sTree[node] = sTree[node<<1]+sTree[node<<1|1];
            }
        }


        void update_point(int index, int val)			// O(log n)
        {
            index += N - 1;
            sTree[index] += val;
            while(index>1)
            {
                index >>= 1;
                sTree[index] = sTree[index<<1] + sTree[index<<1|1];
            }
        }


        void update_range(int i, int j, int val)		// O(log n)
        {
            update_range(1,1,N,i,j,val);
        }

        void update_range(int node, int b, int e, int i, int j, int val)
        {
            if(i > e || j < b)
                return;
            if(b >= i && e <= j)
            {
                sTree[node] += (e-b+1)*val;
                lazy[node] += val;
            }
            else
            {
                int mid = b + e >> 1;
                propagate(node, b, mid, e);
                update_range(node<<1,b,mid,i,j,val);
                update_range(node<<1|1,mid+1,e,i,j,val);
                sTree[node] = sTree[node<<1] + sTree[node<<1|1];
            }

        }
        void propagate(int node, int b, int mid, int e)
        {
            lazy[node<<1] += lazy[node];
            lazy[node<<1|1] += lazy[node];
            sTree[node<<1] += (mid-b+1)*lazy[node];
            sTree[node<<1|1] += (e-mid)*lazy[node];
            lazy[node] = 0;
        }

        int query(int i, int j)
        {
            return query(1,1,N,i,j);
        }

        int query(int node, int b, int e, int i, int j)	// O(log n)
        {
            if(i>e || j <b)
                return 0;
            if(b>= i && e <= j)
                return sTree[node];
            int mid = b + e >> 1;
            propagate(node, b, mid, e);
            int q1 = query(node<<1,b,mid,i,j);
            int q2 = query(node<<1|1,mid+1,e,i,j);
            return q1 + q2;

        }

    }

    static class Scanner
    {
        StringTokenizer st; BufferedReader br;
        public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}
        public Scanner(String s) throws FileNotFoundException {	br = new BufferedReader(new FileReader(new File(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 boolean ready() throws IOException {return br.ready();}
    }
}
