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 «()(())(())».

/* 
Keep solving problems. 
*/
import java.util.*;
import java.io.*;

public class CF380C {

    BufferedReader br;
    PrintWriter out;
    StringTokenizer st;
    boolean eof;
    final long MOD = 1000L * 1000L * 1000L + 7;
    public class STNode {
        int leftIndex;
        int rightIndex;
        int min;
        STNode leftNode;
        STNode rightNode;
    }
    public class SegMin {
        STNode constructSegmentTree(int[] A, int l, int r) {
            if (l == r) {
                STNode node = new STNode();
                node.leftIndex = l;
                node.rightIndex = r;
                node.min = A[l];
                return node;
            }
            int mid = (l + r) / 2;
            STNode leftNode = constructSegmentTree(A, l, mid);
            STNode rightNode = constructSegmentTree(A, mid + 1, r);
            STNode root = new STNode();
            root.leftIndex = leftNode.leftIndex;
            root.rightIndex = rightNode.rightIndex;
            root.min = Math.min(leftNode.min, rightNode.min);
            root.leftNode = leftNode;
            root.rightNode = rightNode;
            return root;
        }

        int getMin(STNode root, int l, int r) {
            if (root.leftIndex >= l && root.rightIndex <= r) {
                return root.min;
            }
            if (root.rightIndex < l || root.leftIndex > r) {
                return Integer.MAX_VALUE;
            }
            return Math.min(getMin(root.leftNode, l, r), getMin(root.rightNode, l, r));
        }

        int updateValueAtIndex(STNode root, int index, int newValue) {
            int res;
            if(root.leftIndex == root.rightIndex && index == root.leftIndex) {
                // We actually reached to the leaf node to be updated
                res = newValue;
                root.min = newValue;
                return res;
            }
            int mid = (root.leftIndex + root.rightIndex) / 2;
            if (index <= mid) {
                res = updateValueAtIndex(root.leftNode, index, newValue);
            } else {
                res = updateValueAtIndex(root.rightNode, index, newValue);
            }
            root.min = Math.min(res, root.min);
            return root.min;
        }
    }


    void solve() throws IOException {
        char[] arr = nextString().toCharArray();
        int m = nextInt();
        int n = arr.length;
        List<Integer> res = new ArrayList<>();
        SegMin seg = new SegMin();
        int[] list = new int[1 + n];
        for(int i = 1; i <= n; i++) {
            list[i] = list[i - 1] + (arr[i - 1] == '(' ? 1 : -1);
        }
        STNode root = seg.constructSegmentTree(list, 0, list.length - 1);
        for(int i = 0; i < m; i++) {
            int l = nextInt() - 1;
            int r = nextInt();
            int minBalance = seg.getMin(root, l, r);
            int leftBalance = list[l];
            int rightBalance = list[r];
            int skipOpen = leftBalance - minBalance;
            int skipClose = rightBalance - minBalance;

            res.add(r - l - skipOpen - skipClose);
        }
        for(int v : res) {
            outln(v);
        }
    }
    void shuffle(int[] a) {
        int n = a.length;
        for(int i = 0; i < n; i++) {
            int r = i + (int) (Math.random() * (n - i));
            int tmp = a[i];
            a[i] = a[r];
            a[r] = tmp;
        }
    }
    private void outln(Object o) {
        out.println(o);
    }
    private void out(Object o) {
        out.print(o);
    }
    public CF380C() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        solve();
        out.close();
    }
    public static void main(String[] args) throws IOException {
        new CF380C();
    }

    public long[] nextLongArr(int n) throws IOException{
        long[] res = new long[n];
        for(int i = 0; i < n; i++)
            res[i] = nextLong();
        return res;
    }
    public int[] nextIntArr(int n) throws IOException {
        int[] res = new int[n];
        for(int i = 0; i < n; i++)
            res[i] = nextInt();
        return res;
    }
    public String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                eof = true;
                return null;
            }
        }
        return st.nextToken();
    }
    public String nextString() {
        try {
            return br.readLine();
        } catch (IOException e) {
            eof = true;
            return null;
        }
    }
    public int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }
    public long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }
    public double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
}

