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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Stream;

import static java.util.Arrays.asList;
import static java.util.stream.Collectors.toList;

/**
 * https://codeforces.com/problemset/problem/381/E
 */
public class Program_381_E {
    private static BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));

    private static List<Integer> readInts() throws IOException {
        return Stream.of(buffer.readLine().split(" ")).map(Integer::parseInt).collect(toList());
    }

    static class Node {
        // Длина максимальной правильной подпоследовательности
        int len;
        // Количество несбалансированных закрывающих скобок
        int extra_close;
        // Количество несбалансированных открывающих скобок
        int extra_open;

        public Node(int len, int extra_close, int extra_open) {
            this.len = len;
            this.extra_close = extra_close;
            this.extra_open = extra_open;
        }
    }

    abstract static class SegTree<T> {
        private int n;
        private List<T> tree;

        public SegTree(List<T> leafs) {
            this.n = leafs.size();
            this.tree = new ArrayList<>(2 * n - 1);
            for (int i = 0; i < 2 * n - 1; i++) {
                tree.add(null);
            }
            buildNode(0, leafs);
        }

        private T buildNode(int v, List<T> leafs) {
            T result;
            if (v >= n - 1) {
                result = leafs.get(v - (n - 1));
            } else {
                T left = buildNode(v * 2 + 1, leafs);
                T right = buildNode(v * 2 + 2, leafs);
                result = combine(asList(left, right));
            }
            tree.set(v, result);
            return result;
        }

        private List<T> nodes_left = new ArrayList<>();
        private List<T> nodes_right = new ArrayList<>();

        List<T> decompose(int l, int r) {
            nodes_left.clear();
            nodes_right.clear();
            //
            int left = (n - 1) + l;
            int right = (n - 1) + r;
            while (left < right) {
                if (left % 2 == 0) {
                    nodes_left.add(tree.get(left++));
                }
                if (right % 2 == 0) {
                    nodes_right.add(tree.get(--right));
                }
                left = (left - 1) / 2;
                right = (right - 1) / 2;
            }
            for (int i = nodes_right.size() - 1; i >= 0; i--) {
                nodes_left.add(nodes_right.get(i));
            }
            return nodes_left;
        }

        T query(int l, int r) {
            List<T> decomposed = decompose(l, r);
            return combine(decomposed);
        }

        abstract T combine(List<T> nodes);
    }

    static class Tree extends SegTree<Node> {
        public Tree(List<Node> leafs) {
            super(leafs);
        }

        Node combine(List<Node> nodes) {
            int opened = 0;
            int extra_close = 0;
            int len = 0;
            for (Node node : nodes) {
                len += node.len;
                int close = node.extra_close;
                while (close != 0) {
                    if (opened == 0) {
                        extra_close += close;
                        close = 0;
                    } else {
                        if (close >= opened) {
                            len += opened * 2;
                            close -= opened;
                            opened = 0;
                        } else {
                            opened -= close;
                            len += close * 2;
                            close = 0;
                        }
                    }
                }
                opened += node.extra_open;
            }
            return new Node(len, extra_close, opened);
        }
    }

    static class SumSegTree extends SegTree<Integer> {
        SumSegTree(List<Integer> ints) {
            super(ints);
        }

        @Override
        Integer combine(List<Integer> nodes) {
            return nodes.stream().reduce(Integer::sum).orElse(0);
        }
    }

    private static void test() {
        List<Integer> array = new ArrayList<>();
        for (int size = 1; size <= 32; size++) {
            array.add(size);
            SumSegTree tree = new SumSegTree(array);
            //
            for (int i = 0; i < array.size(); i++) {
                assert 0 == tree.query(i, i);
                for (int j = i; j < array.size(); j++) {
                    int sum = 0;
                    for (int k = i; k <= j; k++) {
                        sum += array.get(k);
                    }
                    assert sum == tree.query(i, j + 1);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
//        test();
        String s = buffer.readLine();
        List<Node> leafs = new ArrayList<>(s.length());
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                leafs.add(new Node(0, 0, 1));
            } else {
                leafs.add(new Node(0, 1, 0));
            }
        }
        Tree tree = new Tree(leafs);
        int k = Integer.parseInt(buffer.readLine());
        List<Integer> answers = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            List<Integer> ints = readInts();
            answers.add(tree.query(ints.get(0) - 1, ints.get(1)).len);
        }
        System.out.println(String.join("\n", answers.stream().map(Object::toString).collect(toList())));
    }
}
