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.util.Arrays;
import java.util.Comparator;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

public class C380 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        char[] S = in.next().toCharArray();
        int Q = in.nextInt();
        Query[] queries = new Query[Q];
        Query[] sortedQueries = new Query[Q];
        for (int q=0; q<Q; q++) {
            Query query = new Query();
            query.L = in.nextInt();
            query.R = in.nextInt();
            queries[q] = sortedQueries[q] = query;
        }
        Arrays.sort(sortedQueries, new Comparator<Query>() {
            @Override
            public int compare(Query o1, Query o2) {
                return o1.R - o2.R;
            }
        });
        int qIdx = 0;
        BIT bit = new BIT(S.length+1);
        Deque<Integer> list = new LinkedList<>();
        for (int i=1; i<=S.length; i++) {
            char c = S[i-1];
            if (c == '(') {
                list.add(i);
            } else if (!list.isEmpty()) {
                int left = list.removeLast();
                bit.update(1, 1);
                bit.update(left+1, -1);
            }
            while (qIdx < Q && sortedQueries[qIdx].R == i) {
                sortedQueries[qIdx].answer = bit.read(sortedQueries[qIdx].L);
                qIdx++;
            }
        }
        StringBuilder output = new StringBuilder();
        for (Query query : queries) {
            output.append(2*query.answer).append('\n');
        }
        System.out.print(output);
    }

    static class BIT {
        final long[] array;
        final int maxIndex;
        
        BIT(int maxIndex) {
            this.maxIndex = maxIndex;
            array = new long[maxIndex+1];
        }

        long read(int idx) {
            long sum = 0;
            while (idx > 0){
                sum += array[idx];
                idx -= (idx & -idx);
            }
            return sum;
        }

        void update(int idx, long val) {
            while (idx <= maxIndex){
                array[idx] += val;
                idx += (idx & -idx);
            }
        }
    }

    static class Query {
        int L;
        int R;
        long answer;
    }

}
