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

public class Main {
    static PrintWriter pw;
    static Scanner sc;
    static int[] a, b,  dp[];
    static long ceildiv(long x, long y){ return (x+y-1)/y;}
    public static void main(String[] args) throws Exception {
        sc = new Scanner(System.in);
        pw = new PrintWriter(System.out);
        char[] arr=sc.nextLine().toCharArray();
        int len=1;
        while(len<arr.length)
            len<<=1;
        char[] a=new char[len];
        for(int i=0; i<arr.length; i++)
            a[i]=arr[i];
        SegmentTree stree= new SegmentTree(a);
        int q=sc.nextInt();
        while(q-->0)
            pw.println(stree.query(0, 0, a.length-1, sc.nextInt()-1, sc.nextInt()-1).com*2);
        pw.close();
    }
    static void printArr(int[] arr){
        for(int i=0; i<arr.length-1; i++)
            pw.print(arr[i]+" ");
        pw.println(arr[arr.length-1]);
    }
    static void printArr(long[] arr){
        for(int i=0; i<arr.length-1; i++)
            pw.print(arr[i]+" ");
        pw.println(arr[arr.length-1]);
    }
    static void printArr(Integer[] arr){
        for(int i=0; i<arr.length; i++)
            pw.print(arr[i]+" ");
        pw.println();
    }
    static void printArr(char[] arr){
        for(int i=0; i<arr.length; i++)
            pw.print(arr[i]);
        pw.println();
    }
    static void printArr(ArrayList list){
        for(int i=0; i<list.size(); i++)
            pw.print(list.get(i)+" ");
        pw.println();
    }
    static class Scanner {
        StringTokenizer st;
        BufferedReader br;
        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public Scanner(FileReader r) {
            br = new BufferedReader(r);
        }

        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 {
            return Double.parseDouble(next());
        }

        public int[] nextArr(int n) throws IOException {
            int[] arr = new int[n];
            for (int i = 0; i < arr.length; i++)
                arr[i] = nextInt();
            return arr;
        }
        public Integer[] nextsort(int n) throws IOException{
            Integer[] arr=new Integer[n];
            for(int i=0; i<n; i++)
                arr[i]=nextInt();
            return arr;
        }
        public Pair nextPair() throws IOException{
            return new Pair(nextInt(), nextInt());
        }
        public Pair[] nextPairArr(int n) throws IOException{
            Pair[] arr=new Pair[n];
            for(int i=0; i<n; i++)
                arr[i]=new Pair(nextInt(), nextInt());
            return arr;
        }
        public boolean ready() throws IOException {
            return br.ready();
        }
    }
    static class Pair implements Comparable<Pair>{
        int x;
        int y;
        public Pair(int x, int y) {
            this.x=x;
            this.y=y;
        }
        public int hashCode() {
            return this.x*1000+this.y;
        }
        public int compareTo(Pair p){
            return this.x-p.x;
        }
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (this.getClass() != obj.getClass()) {
                return false;
            }
            Pair p = (Pair) obj;
            return this.x==p.x && this.y==p.y;
        }
        public boolean equal(Pair p){
            if(this.x==p.x)
                return this.y==p.y;
            if(this.x==p.y)
                return this.y==p.x;
            else
                return false;
        }
        public Pair clone(){
            return new Pair(x, y);
        }
        public String toString(){
            return this.x+" "+this.y;
        }
    }
    static class Triple{
        int op, com, clos;
        public Triple(int x, int y, int z){
            this.op=x;
            this.com=y;
            this.clos=z;
        }
        public  String toString(){
            return op+" "+com+" "+clos;
        }
//        public int hashCode(){
//            return this.x*100+this.y;
//        }
//        public boolean equals(Object obj){
//            if (obj == null) {
//                return false;
//            }
//            if (this.getClass() != obj.getClass()) {
//                return false;
//            }
//            Triple t = (Triple) obj;
//            return this.x==t.x && this.y==t.y && this.z==t.z;
//        }
    }
    static class SegmentTree{
        Triple[] tree;
        char[] arr;
        public SegmentTree(char[] arr){
            this.arr=arr.clone();
            tree=new Triple[arr.length*2-1];
            build(0, 0, arr.length-1);
        }
        public void build(int i, int l, int r){
            if(l==r){
                if(arr[l]=='(')
                    tree[i]=new Triple(1, 0, 0);
                else if(arr[l]==')')
                    tree[i]=new Triple(0,0, 1);
                else
                    tree[i]=new Triple(0,0,0);
            }else{
                int left=2*i+1, right=2*i+2;
                int mid=(l+r)/2;
                build(left, l, mid);
                build(right, mid+1, r);
                tree[i]=add(tree[left], tree[right]);
            }
        }
        public Triple add(Triple left, Triple right){
            int min=Math.min(left.op, right.clos);
            return new Triple(left.op+right.op-min, left.com+right.com+min, left.clos+right.clos-min);
        }
        public Triple query(int node, int l, int r, int i, int j){
            if(l>j || r<i)
                return new Triple(0, 0, 0);
            if(l>=i && r<=j){
                return tree[node];
            }else{
                int left=2*node+1, right=2*node+2, mid=(l+r)/2;
                return add(query(left, l, mid, i, j), query(right, mid+1, r, i, j));
            }
        }
//        public void update(int node, int l, int r, int i, int j, int x){
//            if(l>j || r<i)
//                return;
//            if(l>=i && r<=j){
//                tree[node]|=x;
//                lazy[node]|=x;
//            }else{
//                int left=2*node+1, right=2*node+2, mid=(l+r)/2;
//                propagate(node, left, right);
//                update(left, l, mid, i, j, x);
//                update(right, mid+1, r, i, j, x);
//                tree[node]=tree[left]&tree[right];
//            }
//        }
//        public void propagate(int i, int l, int r){
//            lazy[l]|=lazy[i];
//            lazy[r]|=lazy[i];
//            tree[l]|=lazy[i];
//            tree[r]|=lazy[i];
//            lazy[i]=0;
//        }
//        public void propagateAll(int i, int l, int r){
//            if(l==r)
//                return;
//            int left=2*i+1, right=2*i+2, mid=(l+r)/2;
//            propagate(i, left, right);
//            propagateAll(left, l, mid); propagateAll(right, mid+1, r);
//        }
//        public void or(int[] arr, int x, int node){
//            for(int i=0; i<30; i++)
//                arr[i]=(x&(1<<i))==0?arr[i]:1;
//        }
//        public int[] and(int[] a, int[] b){
//            int[] c=new int[30];
//            for(int i=0; i<30; i++)
//                c[i]=Math.min(a[i], b[i]);
//            return c;
//        }
//        public long valueOf(int[] arr){
//            long ans=0l;
//            for(int i=0; i<30; i++)
//                ans+=arr[i]*1l*(1<<i);
//            return ans;
//        }
//        public int[] toArray(int x){
//            int[] arr=new int[30];
//            for(int i=0; i<20; i++)
//                arr[i]=(x&(1<<i))==0?0:1;
//            return arr;
//        }
    }
    static class FenwickTree{
        long[] fen;
        public FenwickTree(int[] arr){
            fen=new long[arr.length+1];
        }
        public long query(int i, int j){
            return query(j)-query(i-1);
        }
        public long query(int x){
            long sum=0;
            while(x>0){
                sum+=fen[x];
                x^=x&-x;
            }
            return sum;
        }
        public void update(int i, int x){
            for(; i<fen.length; i+=i&-i)
                fen[i]+=x;
        }
    }
}