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.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.ArrayList;
import java.util.Comparator;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author pva10795
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		Scanner in = new Scanner(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		Task solver = new Task();
		solver.solve(1, in, out);
		out.close();
	}
}

class Task {

    int t[], add[];

    void push(int v, int tl, int tr) {
        if (add[v] != 0) {
            if (tl != tr) add[v * 2] += add[v];
            if (tl != tr) add[v * 2 + 1] += add[v];
            t[v] += add[v];
            add[v] = 0;
        }
    }

    void upd(int v, int tl, int tr, int l, int r, int x) {
        push(v, tl, tr);
        if (l > r) return;
        if (tl == l && tr == r) {
            add[v] += x;
            push(v, tl, tr);
            return;
        }
        int tm = (tl + tr) >> 1;
        upd(v * 2, tl, tm, l, Math.min(r, tm), x);
        upd(v * 2 + 1, tm + 1, tr, Math.max(tm + 1, l), r, x);
        t[v] = Math.max(t[v * 2], t[v * 2 + 1]);
    }

    int get(int v, int tl, int tr, int x) {
        push(v, tl, tr);
        if (tl == tr) return t[v];
        int tm = (tl + tr) >> 1;
        if (x <= tm) return get(v * 2, tl, tm, x);
        else return get(v * 2 + 1, tm + 1, tr, x);
    }

    public void solve(int testNumber, Scanner in, PrintWriter out) {
        String s = in.nextToken();
        int len = s.length();
        int n = in.nextInt();
        t = new int[4 * len];
        add = new int[4 * len];
        final int l[] = new int[n], r[] = new int[n], ans[] = new int[n];
        Integer p[] = new Integer[n];
        for (int i = 0; i < n; i++) {
            l[i] = in.nextInt();
            r[i] = in.nextInt();
            l[i]--; r[i]--;
            p[i] = i;
        }
        Arrays.sort(p, new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                if (l[a] != l[b]) {
                    return Integer.compare(l[a], l[b]);
                }
                return Integer.compare(r[a], r[b]);
            }
        });

        int cur = n - 1;

        ArrayList<Integer> v = new ArrayList<Integer>();
        for (int i = len - 1; i >= 0; i--) {
            if (s.charAt(i) == ')') {
                v.add(i);
            } else {
                if (v.size() > 0) {
                    upd(1, 0, len - 1, v.get(v.size() - 1), len - 1, 1);
                    v.remove(v.size() - 1);
                }
            }
            while (cur >= 0 && l[p[cur]] == i) {
                ans[p[cur]] = get(1, 0, len - 1, r[p[cur]]);
                cur--;
            }
        }
        for (int i = 0; i < n; i++) out.println(2 * ans[i]);
    }

}

class Scanner {
    BufferedReader in;
    StringTokenizer tok;

    public Scanner(InputStream in) {
        this.in = new BufferedReader(new InputStreamReader(in));
        tok = new StringTokenizer("");
    }

    private String tryReadNextLine() {
        try {
            return in.readLine();
        } catch (Exception e) {
            throw new InputMismatchException();
        }
    }

    public String nextToken() {
        while (!tok.hasMoreTokens()) {
            tok = new StringTokenizer(next());
        }
        return tok.nextToken();
    }

    public String next() {
        String newLine = tryReadNextLine();
        if (newLine == null)
            throw new InputMismatchException();
        return newLine;
    }

    public int nextInt() {
        return Integer.parseInt(nextToken());
    }

    }

