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 Main {
    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }

    public static void main(String[] args) {
        InputStream inputStream = System.in;
        InputReader in = new InputReader(inputStream);

        OutputStream outputStream = System.out;
        PrintWriter out = new PrintWriter(outputStream);

        new Main().solve(in, out);
        out.close();
    }

    static class Node {
        int maxLen;
        int open;
        int closed;

        int left;
        int right;


        public Node(int maxLen, int open, int closed, int left, int right) {
            this.maxLen = maxLen;
            this.open = open;
            this.closed = closed;
            this.left = left;
            this.right = right;
        }

        public Node(Node other) {
            this(other.maxLen, other.open, other.closed, other.left, other.right);
        }

        public Node(int left, int right) {
            this(0, 0, 0, left, right);
        }

        public static Node merge(Node lhs, Node rhs) {
            int t = Math.min(lhs.open, rhs.closed);
            int newMaxLen = lhs.maxLen + rhs.maxLen + 2 * t;
            int newOpen = lhs.open + rhs.open - t;
            int newClosed = lhs.closed + rhs.closed - t;
            int left = lhs.left;
            int right = rhs.right;
            return new Node(newMaxLen, newOpen, newClosed, left, right);
        }
    }

    public static ArrayList<Node> makeSegmentTree(char[] brackets) {
        int initLen = brackets.length;
        int expLen = 1;
        while (expLen < initLen) {
            expLen *= 2;
        }

        int treeLen = expLen * 2 - 1;
        ArrayList<Node> tree = new ArrayList<>(Collections.nCopies(treeLen, null));
        int firstElemInd = treeLen - expLen;

        for (int offset = 0; offset < initLen; ++offset) {
            int open = (brackets[offset] == '(' ? 1 : 0);
            int closed = (open == 1 ? 0 : 1);
            tree.set(firstElemInd + offset, new Node(0, open, closed, offset, offset));
        }

        for (int offset = initLen; offset < expLen; ++offset) {
            tree.set(firstElemInd + offset, new Node(offset, offset));
        }

        for (int i = firstElemInd - 1; i >= 0; --i) {
            tree.set(i, Node.merge(tree.get(i * 2 + 1), tree.get(i * 2 + 2)));
        }

        return tree;
    }

    public static Node maxLenQuery(ArrayList<Node> tree, int from, int to, int ind) {
        Node node = tree.get(ind);
        int left = node.left;
        int right = node.right;

        if (right < from || left > to) {
            return new Node(left, right);
        } else if (left >= from && right <= to) {
            return new Node(node);
        } else {
            Node lhsResult = maxLenQuery(tree, from, to, ind * 2 + 1);
            Node rhsResult = maxLenQuery(tree, from, to, ind * 2 + 2);
            return Node.merge(lhsResult, rhsResult);
        }
    }

    public void solve(InputReader in, PrintWriter out) {
        String line = in.next();
        char[] brackets = line.toCharArray();
        ArrayList<Node> tree = makeSegmentTree(brackets);
        int n = in.nextInt();

        int from, to;
        for (int i = 0; i < n; ++i) {
            from = in.nextInt();
            to = in.nextInt();
            --from;
            --to;
            Node result = maxLenQuery(tree, from, to, 0);
            out.println(result.maxLen);
        }
    }
}