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 Parens {

    static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer in;

    static int nextInt() throws IOException {
        in.nextToken();
        return (int)in.nval;
    }

    static class ParGroup {
        int open, correct, closed;

        ParGroup(int o, int r, int c) {
            open = o; correct = r; closed = c;
        }

        static ParGroup merge(ParGroup l, ParGroup r) {
            int matched = Math.min(l.open, r.closed);
            return new ParGroup(l.open + r.open - matched,
                                l.correct + r.correct + (matched << 1),
                                l.closed + r.closed - matched);
        }

        public String toString() {
            return String.format("<%s,%s,%s>", open, correct, closed);
        }

        static ParGroup empty = new ParGroup(0, 0, 0);
        static ParGroup oneOpen = new ParGroup(1, 0, 0);
        static ParGroup oneClosed = new ParGroup(0, 0, 1);
    }

    static class Tree {
        int from, to;
        Tree left, right;
        ParGroup pars;

        Tree(ParGroup _pars, Tree _l, Tree _r, int _f, int _t) {
            left = _l; right = _r; from = _f; to = _t; pars = _pars;
        }

        static Tree merge(Tree l, Tree r) {
            return new Tree(ParGroup.merge(l.pars, r.pars), l, r, l.from, r.to);
        }

        static Tree leaf(ParGroup _pars, int _f, int _t) {
            return new Tree(_pars, null, null, _f, _t);
        }

        @Override
        public String toString() {
            String l = (left == null) ? "" : (", " + left);
            String r = (right == null) ? "" : (", " + right);
            return "{" + pars + l + r + "}";
        }

        ParGroup lookup(int f, int t) {
            if (f <= from && t >= to) return pars;
            if (f >= to || t <= from) return ParGroup.empty;
            return ParGroup.merge(left.lookup(f, t), right.lookup(f, t));
        }
    }

    public static void main(String[] args) throws Exception {
        String parseq = br.readLine();
        int n = parseq.length();
        Tree[] prevLevel = new Tree[n];
        Tree[] currLevel;
        for (int i = 0; i < n; i++)
            prevLevel[i] = Tree.leaf(parseq.charAt(i) == '(' ? ParGroup.oneOpen : ParGroup.oneClosed,
                                     i, i+1);

        int t = (n + 1) / 2;
        do {
            currLevel = new Tree[t];
            for (int i = 0; i < t; i++) {
                Tree left = prevLevel[i*2];
                if (prevLevel.length < (i + 1) * 2) {
                    currLevel[i] = left;
                } else {
                    currLevel[i] = Tree.merge(left, prevLevel[i*2+1]);
                }
            }
            prevLevel = currLevel;
            t = (t == 1) ? 0 : ((t + 1) / 2);
        } while (t > 0);

        Tree root = prevLevel[0];
        // System.out.println(root);

        // Queries
        in = new StreamTokenizer(br);
        int q = nextInt();
        for (int i = 0; i < q; i++)
            out.write("" + root.lookup(nextInt()-1, nextInt()).correct + "\n");
        out.flush();
    }
}
