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.StringTokenizer;

import static java.lang.Integer.parseUnsignedInt;
import static java.lang.Math.min;
import static java.nio.charset.StandardCharsets.UTF_8;

public class Main {

    public static void main(String[] args) throws IOException {
        try (BufferedReader in = new BufferedReader(new InputStreamReader(System.in, UTF_8));
             BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out, UTF_8))) {
            char[] str = in.readLine().trim().toCharArray();
            int m = parseUnsignedInt(in.readLine().trim());
            int[] left = new int[m];
            int[] right = new int[m];
            for (int i = 0; i < m; i++) {
                StringTokenizer tokens = new StringTokenizer(in.readLine());
                left[i] = parseUnsignedInt(tokens.nextToken()) - 1;
                right[i] = parseUnsignedInt(tokens.nextToken()) - 1;
            }
            int[] heights = new int[str.length + 1];
            int height = 0;
            SegmentTreeMin tree = new SegmentTreeMin(str.length + 1);
            for (int i = 0; i < str.length; i++) {
                if (str[i] == '(') {
                    height++;
                } else {
                    height--;
                }
                heights[i + 1] = height;
                tree.addValue(i + 1, i + 2, height);
            }
            for (int i = 0; i < m; i++) {
                int l = left[i];
                int r = right[i];
                long min = tree.getMinimum(l, r + 2);
                long ll = heights[l] - min;
                long rr = heights[r + 1] - min;
                out.write((r + 1 - l - ll - rr) + "");
                out.newLine();
            }
        }
    }

    private static class SegmentTreeMin {

        private final int size;
        private final long[] values;
        private final long[] min;

        public SegmentTreeMin(int size) {
            if (size < 1) {
                throw new IllegalArgumentException("Input size should be positive value");
            }
            this.size = size;
            this.values = new long[size << 2];
            this.min = new long[size << 2];
        }

        /**
         * Adds new value to all elements in [left, right) interval.
         *
         * @param left  left bound
         * @param right right bound
         * @param value value to add
         */
        public void addValue(int left, int right, int value) {
            if (left < 0 || right > size) {
                throw new IllegalArgumentException(
                        "Input left and round bounds should be between zero and segment tree size");
            }
            if (right <= left) {
                throw new IllegalArgumentException(
                        "Input right bound should be greater than left bound");
            }
            addValue(left, right, value, 0, 0, size);
        }

        /**
         * Finds a minimum value on interval [left, right).
         *
         * @param left  left bound
         * @param right right bound
         * @return the minimum on interval
         */
        public long getMinimum(int left, int right) {
            if (left < 0 || right > size) {
                throw new IllegalArgumentException(
                        "Input left and round bounds should be between zero and segment tree size");
            }
            if (right <= left) {
                throw new IllegalArgumentException(
                        "Input right bound should be greater than left bound");
            }
            return getMinimum(left, right, 0, 0, size);
        }

        private void addValue(int left, int right, int value, int pos, int treeLeft, int treeRight) {
            if (left == treeLeft && right == treeRight) {
                min[pos] += value;
                values[pos] += value;
                return;
            }
            int treeMedian = (treeLeft + treeRight) >>> 1;
            if (right <= treeMedian) {
                addValue(left, right, value, 2 * pos + 1, treeLeft, treeMedian);
            } else if (left >= treeMedian) {
                addValue(left, right, value, 2 * pos + 2, treeMedian, treeRight);
            } else {
                addValue(left, treeMedian, value, 2 * pos + 1, treeLeft, treeMedian);
                addValue(treeMedian, right, value, 2 * pos + 2, treeMedian, treeRight);
            }
            min[pos] = min(min[2 * pos + 1], min[2 * pos + 2]) + values[pos];
        }

        private long getMinimum(int left, int right, int pos, int treeLeft, int treeRight) {
            if (left == treeLeft && right == treeRight) {
                return min[pos];
            }
            int treeMedian = (treeLeft + treeRight) >>> 1;
            if (right <= treeMedian) {
                return getMinimum(left, right, 2 * pos + 1, treeLeft, treeMedian) + values[pos];
            }
            if (left >= treeMedian) {
                return getMinimum(left, right, 2 * pos + 2, treeMedian, treeRight) + values[pos];
            }
            return min(getMinimum(left, treeMedian, 2 * pos + 1, treeLeft, treeMedian),
                    getMinimum(treeMedian, right, 2 * pos + 2, treeMedian, treeRight)) + values[pos];
        }
    }
}
