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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.InputStreamReader;
import java.io.InputStream;
import java.io.UnsupportedEncodingException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Dictionary;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;
import java.util.logging.Level;
import java.util.logging.Logger;

public class Main {

    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskD slover = new TaskD();
        slover.solve(in, out);
        out.close();
    }

    static class TaskD {

        Node[] st;
        String s;

        public void solve(InputReader in, PrintWriter out) {
            s = in.next();
            // ST
            st = new Node[4 * s.length()];
            buildST(0, s.length() - 1, 1);
            int m = in.nextInt();
            for (int i = 0; i < m; i++) {
                int u = in.nextInt();
                int v = in.nextInt();
                Node n = get(0, s.length() - 1, u - 1, v - 1, 1);
                out.println(n.current * 2);
            }
        }

        Node get(int l, int r, int u, int v, int id) {
            if (v < l || r < u) {
                return new Node();
            }

            if (u <= l && r <= v) {
                return st[id];
            }

            int mid = (l + r) / 2;
            return add(get(l, mid, u, v, id * 2), get(mid + 1, r, u, v, id * 2 + 1));
        }

        void buildST(int l, int r, int id) {
            if (l == r) {
                if (s.charAt(l) == '(') {
                    st[id] = new Node(0, 1, 0);
                } else {
                    st[id] = new Node(0, 0, 1);
                }
                return;
            }
            int mid = (l + r) / 2;

            buildST(l, mid, id * 2);
            buildST(mid + 1, r, id * 2 + 1);
            st[id] = add(st[id * 2], st[id * 2 + 1]);
        }

        Node add(Node left, Node right) {
            Node rs = new Node();

            int m = Math.min(left.open, right.close);
            rs.current = m + left.current + right.current;
            rs.open = left.open - m + right.open;
            rs.close = left.close + right.close - m;
            return rs;
        }

    }

    static class Node {

        int current = 0;
        int open = 0;
        int close = 0;

        public Node() {
        }

        public Node(int current, int open, int close) {
            this.current = current;
            this.open = open;
            this.close = close;
        }

    }

    static class InputReader {

        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

        public long nextLong() {
            return Long.parseLong(next());
        }
    }

}
