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.Collections.singletonList;
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;
        }
    }

    static class Tree {
        int n;
        String s;
        Node[] tree;
        // Индекс первого элемента последнего слоя
        // Нужен для определения высот при подъёме (чтобы не пропустить lca)
        // Все листья начиная с этого индекса лежат на последнем слое
        // А листья до этого индекса - на предпоследнем
        int last_layer_start;
        int leafs_at_last_layer;

        public Tree(String s) {
            this.s = s;
            this.n = s.length();
            this.tree = new Node[2 * n - 1];
            this.last_layer_start = Integer.highestOneBit(2 * n - 1) - 1;
            this.leafs_at_last_layer = n - (last_layer_start - (n - 1));
            buildNode(0);
        }

        // Определяет индекс листа по индексу исходной последовательности
        private int leaf(int sourceIndex) {
            if (sourceIndex >= leafs_at_last_layer) {
                return (n - 1) + (sourceIndex - leafs_at_last_layer);
            } else {
                return last_layer_start + sourceIndex;
            }
        }

        // Выполняет обратное преобразование
        private int sourceIndex(int leaf) {
            if (leaf >= last_layer_start) {
                return leaf - last_layer_start;
            } else {
                return leaf - (n - 1) + leafs_at_last_layer;
            }
        }

        private Node buildNode(int v) {
            Node result;
            if (v >= n - 1) {
                if (s.charAt(sourceIndex(v)) == '(') {
                    result = new Node(0, 0, 1);
                } else {
                    result = new Node(0, 1, 0);
                }
            } else {
                Node left = buildNode(v * 2 + 1);
                Node right = buildNode(v * 2 + 2);
                result = combine(asList(left, right));
            }
            tree[v] = result;
            return result;
        }

        private 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);
        }

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

        List<Node> decompose(int l, int r) {
            nodes_left.clear();
            nodes_right.clear();
            //
            int left_node = leaf(l);
            int right_node = leaf(r);
            if(left_node == right_node) {
                return singletonList(tree[left_node]);
            }
            nodes_left.add(tree[left_node]);
            nodes_right.add(tree[right_node]);
            if (left_node >= last_layer_start && right_node < last_layer_start) {
                // Делаем один подъём из l
                if (left_node % 2 == 1) {
                    // left_node -- левый сын
                    nodes_left.add(tree[left_node + 1]);
                } else {
                    // left_node -- правый сын
                }
                left_node = (left_node - 1) / 2;
            }
            int left_parent = (left_node - 1) / 2;
            int right_parent = (right_node - 1) / 2;
            while (left_parent != right_parent) {
                if (left_node % 2 == 1) {
                    // left_node -- левый сын
                    nodes_left.add(tree[left_node + 1]);
                } else {
                    // left_node -- правый сын
                }
                left_node = left_parent;
                //
                if (right_node % 2 == 1) {
                    // right_node -- левый сын
                } else {
                    // right_node -- правый сын
                    nodes_right.add(tree[right_node - 1]);
                }
                right_node = right_parent;
                //
                left_parent = (left_node - 1) / 2;
                right_parent = (right_node - 1) / 2;
            }
            for (int i = nodes_right.size() - 1; i >= 0; i--) {
                nodes_left.add(nodes_right.get(i));
            }
            return nodes_left;
        }

        int query(int l, int r) {
            List<Node> decomposed = decompose(l, r);
            Node combined = combine(decomposed);
            return combined.len;
        }
    }

    public static void main(String[] args) throws IOException {
        String s = buffer.readLine();
        Tree tree = new Tree(s);
        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) - 1));
        }
        System.out.println(String.join("\n", answers.stream().map(Object::toString).collect(toList())));
    }
}
