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 BracketMain {
    static String s;
    static Node[] st;
    static int n;
    static int num;
    static char[] arr;
    static int[] t;
    static int[] o;
    static int[] c;
    static class Node{
        int pairs;
        int open;
        int closed;
        public Node(int p, int o, int c){
            pairs=p;
            open=o;
            closed=c;
        }
    }
    //x,y refer to the query's interval, i,j refer to the current node's interval, ind is the index of current node on st
    static Node queryUtil(int x, int y, int i, int j, int ind) {

        //current node outside of query's interval
        if (i>y || j<x) {
            return new Node(0, 0, 0);//how to deal with null node
            
        }

        //all of current node contained within query's interval
        if (i>=x && j<=y) return new Node(t[ind], o[ind], c[ind]);

        Node left=queryUtil(x, y, i, (i+j)/2, 2*ind);
        Node right=queryUtil(x, y, (i+j)/2 + 1, j, 2*ind + 1);

        int min=Math.min(left.open, right.closed);
        return new Node(left.pairs+right.pairs+2*min, left.open+right.open-min, left.closed+right.closed-min);
    }
    static int query(int x, int y) {
        //x=1, y=2, n=12
        return queryUtil(x, y, 1, n, 1).pairs;
    }
    static void construct(int i, int j, int ind) {
        //System.out.println("construct: " + num); num++;

        if (i==j) {
        if (arr[i]=='(') o[ind]=1;
        if (arr[i]==')') c[ind]=1;
        return;
        }

        construct(i, (i+j)/2, ind*2);
        construct((i+j)/2 + 1, j, ind*2 + 1);

        int min=Math.min(o[2*ind], c[2*ind+1]);
        t[ind]=t[2*ind]+t[2*ind+1]+2*min;
        o[ind]=o[2*ind]+o[2*ind+1]-min;
        c[ind]=c[2*ind]+c[2*ind+1]-min;
    }

    public static void main(String[] args) throws IOException{
        num=0;

        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        s=in.readLine();
        n=s.length();
        int max_size=(int)(Math.pow(2, 1+(int)(Math.ceil(Math.log(n)/Math.log(2)))));

        t=new int[max_size];
        o=new int[max_size];
        c=new int[max_size];
        int m=Integer.parseInt(in.readLine());
        arr=new char[n+1];
        for (int i=1; i<n+1; i++)
            arr[i]=s.charAt(i-1);

        construct(1, n, 1);

        while (m-->0) {
            String[] str=(in.readLine()).split(" ");
            int x=Integer.parseInt(str[0]);
            int y=Integer.parseInt(str[1]);

            System.out.println(query(x, y));
        }

    }
}