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.lang.*;
import java.io.*;
public class Codechef{
    static int[] a,o,c;
    static char[] s;
    
    static class Triple{
        int a,o,c;
        Triple(int x, int y, int z){
            a=x; o=y; c=z;
        }
    }
    
    static void build(int node, int left, int right){
        if(left>right) return;
        if(left==right){
            if(s[left]=='(') o[node]++;
            else c[node]++;
            return;
        }
        int mid = (left+right)/2;
        build(2*node,left,mid);
        build(2*node+1,mid+1,right);
        int t = Math.min(o[2*node],c[2*node+1]);
        a[node] = a[2*node]+a[2*node+1]+2*t;
        o[node] = o[2*node]+o[2*node+1]-t;
        c[node] = c[2*node]+c[2*node+1]-t;
    }
    
    static Triple query(int node, int left, int right, int i, int j){
        if(right<i || left>j || left>right) return new Triple(0,0,0);
        if(left>=i && right<=j){
            return new Triple(a[node],o[node],c[node]);
        }
        int mid = (left+right)/2;
        Triple l = query(2*node,left,mid,i,j);
        Triple r = query(2*node+1,mid+1,right,i,j);
        int t = Math.min(l.o,r.c);
        return new Triple(l.a+r.a+2*t, l.o+r.o-t, l.c+r.c-t);
    }
    
	public static void main (String[] args) throws java.lang.Exception{
	    PrintWriter out = new PrintWriter(System.out);
	    InputReader sc = new InputReader(System.in);
	    s = (" "+sc.nextToken()).toCharArray();
	    int n = s.length-1;
        a = new int[4*n+1];
        o = new int[4*n+1];
        c = new int[4*n+1];
        build(1,1,n);
	    int m = sc.nextInt();
	    while(m-->0){
	        int l = sc.nextInt();
	        int r = sc.nextInt();
	        out.println(query(1,1,n,l,r).a);
	    }
	    out.close();
	}
	
	public static class InputReader {
        private static final int BUFFER_LENGTH = 1 << 12;
        private InputStream stream;
        private byte[] buf = new byte[BUFFER_LENGTH];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        private int next() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public char nextChar() {
            return (char) skipWhileSpace();
        }

        public String nextToken() {
            int c = skipWhileSpace();
            StringBuilder res = new StringBuilder();
            do {
                res.append((char) c);
                c = next();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public int nextInt() {
            return (int) nextLong();
        }

        public long nextLong() {
            int c = skipWhileSpace();
            long sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = next();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = next();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public double nextDouble() {
            return Double.valueOf(nextToken());
        }

        int skipWhileSpace() {
            int c = next();
            while (isSpaceChar(c)) {
                c = next();
            }
            return c;
        }

        boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
    }
}