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.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.BufferedWriter;
import java.io.PrintStream;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.StringTokenizer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author ayush1617
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		OutputWriter out = new OutputWriter(outputStream);
		TaskE solver = new TaskE();
		solver.solve(1, in, out);
		out.close();
	}
}

class Node{
    int CloseBracket;
    int OpenBracket;
       int ans;
}

class TaskE {

    public void build(String str,Node tree[],int start,int end,int node){
             //       System.out.println(start + " " + end + " " + node);
        if(start>end)
            return ;
        if(start==end){
             tree[node]=new Node();
               if(str.charAt(start)=='('){
                   tree[node].OpenBracket=1;
                   tree[node].CloseBracket=0;
                   tree[node].ans=0;
               }
                else{
                   tree[node].CloseBracket=1;
                   tree[node].OpenBracket=0;
                   tree[node].ans=0;

               }
            return ;
        }

        int mid=(start+end)/2;
        build(str,tree,start,mid,2*node);
        build(str,tree,mid+1,end,2*node+1);


                                  //left                        //right
        int temp=Math.min(tree[2*node].OpenBracket,tree[2*node+1].CloseBracket);
        tree[node]=new Node();
        tree[node].ans = tree[2*node].ans + tree[2*node+1].ans+2*temp;
        tree[node].OpenBracket=tree[2*node].OpenBracket+tree[2*node+1].OpenBracket-temp;
        tree[node].CloseBracket=tree[2*node].CloseBracket+tree[2*node+1].CloseBracket-temp;
    }

    Node query(Node tree[],int start,int end,int l,int r,int node, OutputWriter out){


        if(end<l || start>r)
                return null;

            if(l<=start&&r>=end)
                return tree[node];

            int mid=(start+end)/2;
            Node left=query(tree,start,mid,l,r,2*node,out);
            Node right=query(tree,mid+1,end,l,r,2*node+1,out);
      
            int temp;
            if(left!=null && right!=null){
                temp=Math.min(left.OpenBracket,right.CloseBracket);
            }
            else
            if(left==null){
                 
                return right;

            }
            else{
          
                return left;

            }
          
           Node result=new Node();
            result.ans = left.ans + right.ans+2*temp;
            result.OpenBracket=left.OpenBracket+right.OpenBracket-temp;
            result.CloseBracket=left.CloseBracket+right.CloseBracket-temp;
       
        return result;
    }

    public void print(Node tree[],int start,int end,int node){
        System.out.println(start+" "+end+" "+tree[node].ans);
        if(start==end)
        {
            return;
        }
        int mid=(start+end)/2;
        print(tree, start, mid, 2 * node);
        print(tree,mid+1,end,2*node+1);
    }
    public void solve(int testNumber, InputReader in, OutputWriter out) {

        String str=" "+in.next();
        int m=in.nextInt(),l,r;
        Node tree[]=new Node[4*1000000];
        build(str,tree,1,str.length()-1,1);
       
        for(int i=1;i<=m;i++){
            l=in.nextInt();
            r=in.nextInt();
           
            out.printLine(query(tree,1,str.length()-1,l,r,1,out).ans);
        }

    }
}

class OutputWriter {
     public PrintWriter writer;

    public OutputWriter(OutputStream outputStream) {
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public OutputWriter(Writer writer) {
        this.writer= new PrintWriter(writer);
    }

    public void print(Object...objects) {
        for (int i = 0; i < objects.length; i++) {
            if (i != 0)
                writer.print(' ');
            writer.print(objects[i]);
        }
    }

    public void printLine(Object...objects) {
        print(objects);
        writer.println();
    }

    public void close() {
        writer.close();
    }
}

class InputReader
{
    BufferedReader in;
    StringTokenizer tokenizer=null;

    public InputReader(InputStream inputStream)
    {
        in=new BufferedReader(new InputStreamReader(inputStream));
    }
    public String next()
    {
        try{
            while (tokenizer==null||!tokenizer.hasMoreTokens())
            {
                tokenizer=new StringTokenizer(in.readLine());
            }
            return tokenizer.nextToken();
        }
        catch (IOException e)
        {
            return null;
        }
    }
    public int nextInt()
    {
        return Integer.parseInt(next());
    }
    public Long nextLong(){
        return Long.parseLong(next());
    }
}
