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.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.*;

public class Solution {
    InputStream is;
    PrintWriter out;
    String INPUT = "";
    private byte[] inbuf = new byte[1024];
    public int lenbuf = 0;
    public int ptrbuf = 0;

    Sag_tree tree[];
    char a[];

    class Sag_tree{
        int total,o,c;
    }

    Sag_tree merge(Sag_tree a,Sag_tree b){
        Sag_tree s=new Sag_tree();
        s.total=a.total+b.total+2*Math.min(a.o,b.c);
        s.o=a.o+b.o-Math.min(a.o,b.c);
        s.c=a.c+b.c-Math.min(a.o,b.c);
        return s;
    }

    void build(int node,int start,int end){
        if(start==end){
            tree[node]=new Sag_tree();
            if(a[start]=='(')tree[node].o=1;
            else tree[node].c=1;
        }
        else{
            tree[node]=new Sag_tree();
            int mid=(start+end)/2;
            build(2*node,start,mid);
            build(2*node+1,mid+1,end);
            tree[node]=merge(tree[2*node],tree[2*node+1]);
        }
    }

    Sag_tree query(int node,int start,int end,int l,int r){
        int  mid=(start+end)/2;
        if(start>=l && end<=r){
            return tree[node];
        }
        else if(mid<l){
            return query(2*node+1,mid+1,end,l,r);
        }
        else if(mid>=r){
            return query(2*node,start,mid,l,r);
        }
        else {

            Sag_tree l1=query(2*node,start,mid,l,r);
            Sag_tree l2=query(2*node+1,mid+1,end,l,r);
            return merge(l1,l2);
        }
    }

    void solve() {
        String ss=ns();
        int n=ss.length();
        a=ss.toCharArray();
        tree=new Sag_tree[4*n];
       /* for (int i = 0; i <33 ; i++) {
            tree[i]=new Sag_tree();
        }*/
        build(1,0,n-1);
       /* for (int i = 0; i <33 ; i++) {
            out.println(i+" "+tree[i].total+" "+tree[i].o+" "+tree[i].c);
        }*/
        int q=ni();
        while (q-->0){
            out.println(query(1,0,n-1,ni()-1,ni()-1).total);
        }
    }

    void run() throws Exception {
        this.is = (InputStream)(this.INPUT.isEmpty() ? System.in : new ByteArrayInputStream(this.INPUT.getBytes()));
        this.out = new PrintWriter(System.out);
        long s = System.currentTimeMillis();
        this.solve();
        this.out.flush();
        if (!this.INPUT.isEmpty()) {
            tr(System.currentTimeMillis() - s + "ms");
        }

    }

    public static void main(String[] args) throws Exception {
        (new Solution()).run();
    }

    private int readByte() {
        if (this.lenbuf == -1) {
            throw new InputMismatchException();
        } else {
            if (this.ptrbuf >= this.lenbuf) {
                this.ptrbuf = 0;

                try {
                    this.lenbuf = this.is.read(this.inbuf);
                } catch (IOException var2) {
                    throw new InputMismatchException();
                }

                if (this.lenbuf <= 0) {
                    return -1;
                }
            }

            return this.inbuf[this.ptrbuf++];
        }
    }

    private boolean isSpaceChar(int c) {
        return c < 33 || c > 126;
    }

    private int skip() {
        int b;
        while((b = this.readByte()) != -1 && this.isSpaceChar(b)) {
            ;
        }

        return b;
    }

    private double nd() {
        return Double.parseDouble(this.ns());
    }

    private char nc() {
        return (char)this.skip();
    }

    private int[][] matix(int y1, int y2) {
        int[][] a = new int[y1][y2];

        for(int i = 0; i < y1; ++i) {
            for(int j = 0; j < y2; ++j) {
                a[i][j] = this.ni();
            }
        }

        return a;
    }

    private String ns() {
        int b = this.skip();

        StringBuilder sb;
        for(sb = new StringBuilder(); !this.isSpaceChar(b); b = this.readByte()) {
            sb.appendCodePoint(b);
        }

        return sb.toString();
    }

    private char[] ns(int n) {
        char[] buf = new char[n];
        int b = this.skip();

        int p;
        for(p = 0; p < n && !this.isSpaceChar(b); b = this.readByte()) {
            buf[p++] = (char)b;
        }

        return n == p ? buf : Arrays.copyOf(buf, p);
    }

    private char[][] nm(int n, int m) {
        char[][] map = new char[n][];

        for(int i = 0; i < n; ++i) {
            map[i] = this.ns(m);
        }

        return map;
    }

    private int[] na(int n) {
        int[] a = new int[n];

        for(int i = 0; i < n; ++i) {
            a[i] = this.ni();
        }

        return a;
    }

    private int ni() {
        int num = 0;
        boolean minus = false;

        int b;
        while((b = this.readByte()) != -1 && (b < 48 || b > 57) && b != 45) {
            ;
        }

        if (b == 45) {
            minus = true;
            b = this.readByte();
        }

        while(b >= 48 && b <= 57) {
            num = num * 10 + (b - 48);
            b = this.readByte();
        }

        return minus ? -num : num;
    }

    private long nl() {
        long num = 0L;
        boolean minus = false;

        int b;
        while((b = this.readByte()) != -1 && (b < 48 || b > 57) && b != 45) {
            ;
        }

        if (b == 45) {
            minus = true;
            b = this.readByte();
        }

        while(b >= 48 && b <= 57) {
            num = num * 10L + (long)(b - 48);
            b = this.readByte();
        }

        return minus ? -num : num;
    }

    private static void tr(Object... o) {
        System.out.println(Arrays.deepToString(o));
    }
}
