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 «()(())(())».
//package codeforces.Brackets;

import java.util.*;
import java.io.*;

import static java.lang.Integer.parseUnsignedInt;

public class Brackets {
    private static String brackets;
    private static int[] maximum;
    private static int[] opened;
    private static int[] closed;

    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        FastScanner(InputStream stream) {
            try {
                br = new BufferedReader(new InputStreamReader(stream), 65536);
            } catch (Exception e) {
                e.printStackTrace();
            }
        }

        String nextLine() throws IOException {
            return br.readLine();
        }

        int[] nextVals() throws IOException {
            StringTokenizer tokens = new StringTokenizer(br.readLine());
            return new int[]{parseUnsignedInt(tokens.nextToken()), parseUnsignedInt(tokens.nextToken())};
        }
        int nextInt() throws IOException {

            return parseUnsignedInt(br.readLine().trim());
        }
    }

    private static void build(int index, int left, int right) {
        // check and early return
        if (left == right) {
            if (brackets.charAt(left) == '('){
                opened[index] = 1;
            } else {
                closed[index] = 1;
            }
            maximum[index] = 1;
            return;
        }
        int m = (left + right) / 2;
        int leftInd = index * 2;
        int rightInd = index * 2 + 1;

        build(leftInd, left, m);
        build(rightInd, m + 1, right);

        int minV = Math.min(opened[leftInd], closed[rightInd]);

        maximum[index] = maximum[leftInd] + maximum[rightInd];
        opened[index] = opened[leftInd] + opened[rightInd] - minV;
        closed[index] = closed[leftInd] + closed[rightInd] - minV;
    }

    private static int[] getMaximum(int ind, int l, int r, int i, int j) {
        // check boundaries
        if (l >= i && r <= j) {
            return new int[]{maximum[ind], opened[ind], closed[ind]};
        }

        if (r < i || l > j) {
            return new int[]{0, 0, 0};
        }


        int m = (l + r) / 2;
        int leftInd = ind * 2;
        int rightInd = ind * 2 + 1;

        int[] first = getMaximum(leftInd, l, m, i, j);
        int[] second = getMaximum(rightInd, m + 1, r, i, j);

        int minV = Math.min(first[1], second[2]);
        return new int[]{first[0] + second[0], first[1] + second[1] - minV, first[2] + second[2] - minV};
    }

    public static void main(String[] argv) throws IOException {
        BufferedOutputStream writer = new BufferedOutputStream(System.out);
        FastScanner sc = new FastScanner(System.in);
        brackets = sc.nextLine();
        int m = sc.nextInt();
        int sizeOfS = (int)Math.pow(2., 2. + Math.log(brackets.length())/Math.log(2)) + 1;
        maximum = new int[sizeOfS];
        opened = new int[sizeOfS];
        closed = new int[sizeOfS];

        int[][] queries = new int[m][2];
        for (int i = 0; i < m; i++) {
            int[] temp = sc.nextVals();
            queries[i][0] = temp[0] - 1;
            queries[i][1] = temp[1] - 1;
        }

        build(1, 0, brackets.length()-1);
        int[] result;
        for (int i = 0; i < queries.length; i++) {
            int left = queries[i][0];
            int right = queries[i][1];
            result = getMaximum(1, 0, brackets.length()-1, left, right);
            String res = Integer.toString(result[0]-result[1]-result[2]) + "\n";
            writer.write(res.getBytes());
        }
        writer.flush();
        writer.close();

    }


}