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 SerejaAndBrackets{
    static int[] tree;
    static int n;
    static void build(int[] aa) {
        for (int i = 0; i < n; i++)
            tree[n + i] = aa[i];
        for (int i = n - 1; i > 0; i--)
            tree[i] = Math.min(tree[i << 1] , tree[i << 1 | 1]);
    }
    static int query(int l, int r) {
        int a = 0x3f3f3f3f;
        for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
            if ((l & 1) == 1)
                a = Math.min(a, tree[l++]);
            if ((r & 1) == 0)
                a = Math.min(a, tree[r--]);
        }
        return a;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        char[] bracket = br.readLine().toCharArray();
        n = bracket.length + 1;
        int[] aa = new int[n];
        int a = 0;
        for (int i = 1; i < n; i++) {
            if (bracket[i - 1] == '(')
                a++;
            else
                a--;
            aa[i] = a;
        }
        tree = new int[n + n];
        build(aa);
        int q = Integer.parseInt(br.readLine());
        while (q-- > 0) {
            StringTokenizer st= new StringTokenizer(br.readLine());
            int left = Integer.parseInt(st.nextToken()) - 1;
            int right = Integer.parseInt(st.nextToken());
            a = query(left, right);
            System.out.println(right - left - (aa[left] - a) - (aa[right] - a));
        }
    }

}
