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.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Stack;

public class E {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        String s = in.readLine();
        int n = Integer.parseInt(in.readLine());
        LinkedList<Point>[] E = new LinkedList[s.length()];
        for (int i = 0; i < E.length; i++)
            E[i] = new LinkedList<Point>();
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            String[] S = in.readLine().split(" ");
            E[Integer.parseInt(S[1]) - 1].add(new Point(i, Integer
                    .parseInt(S[0]) - 1));
        }
        SegmentTree T = new SegmentTree(s.length());
        Stack<Integer> st = new Stack<Integer>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(')
                st.add(i);
            else if (!st.isEmpty())
                T.update(st.pop(), 1);
            for (Point p : E[i])
                ans[p.x] = T.query(p.y, i) * 2;
        }
        for (int i = 0; i < n; i++)
            out.println(ans[i]);
        out.flush();
        out.close();
    }
}

class SegmentTree {
    int[] T;
    int size = 1;
    static int inf;

    // number of leaves u need (0, n-1)
    public SegmentTree(int n) {
        while (size < n)
            size <<= 1;
        T = new int[size << 1];
    }

    public void init(int v) {
        inf = v;
        Arrays.fill(T, 0);
    }

    public void update(int index, int v) {
        index += size;
        T[index] = v;
        while (index > 1) {
            index >>= 1;
            T[index] = T[index << 1] + T[(index << 1) + 1];
        }
    }

    // send query [i,j]
    public int query(int i, int j) {
        return query(1, 0, size - 1, i, j);
    }

    private int query(int node, int b, int e, int i, int j) {
        int p1, p2;
        if (i > e || j < b)
            return 0;
        if (b >= i && e <= j)
            return T[node];
        p1 = query(2 * node, b, (b + e) / 2, i, j);
        p2 = query(2 * node + 1, (b + e) / 2 + 1, e, i, j);
        return p1 + p2;
    }
}
