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.*;
import java.util.*;

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

	static class node {
		public int sq;
		public int lf;
		public int rg;
		node(int sq, int lf, int rg) {
			this.sq = sq;
			this.lf = lf;
			this.rg = rg;
		}
	}

	static class Task {
		int n, m;
		String s;
		node[] seg;

		public void build(int i, int l, int r) {
			if (r - l < 2) {
				try {
					seg[i].sq = 0;
					if (s.charAt(l) == '(')
						seg[i].rg = 1;
					else
						seg[i].lf = 1;
					}
				catch (Exception e) {
					System.out.printf("problem on %d \n", i);
				}
				return ;
			}
			int mid = (l + r) / 2;
			try {
				build(2 * i, l, mid);
				build(2 * i + 1, mid, r);
				seg[i].sq = seg[2 * i].sq + seg[2 * i + 1].sq + 2 * Math.min(seg[2 * i].rg, seg[2 * i + 1].lf);
				seg[i].rg = seg[2 * i].rg + seg[2 * i + 1].rg - Math.min(seg[2 * i].rg, seg[2 * i + 1].lf);
				seg[i].lf = seg[2 * i].lf + seg[2 * i + 1].lf - Math.min(seg[2 * i].rg, seg[2 * i + 1].lf);
			}
			catch (Exception e) {
				System.out.printf("problem2 on %d\n", i);
			}
		}

		public node get(int x, int y, int i, int l, int r) {
			if (x >= r || l >= y) return new node(0, 0, 0);
			if (x <= l && r <= y) return seg[i];
			int mid = (l + r) / 2;
			node A = get(x, y, 2 * i, l, mid);
			node B = get(x, y, 2 * i + 1, mid, r);
			node res = new node(0, 0, 0);
			res.sq = A.sq + B.sq + 2 * Math.min(A.rg, B.lf);
			res.lf = A.lf + B.lf - Math.min(A.rg, B.lf);
			res.rg = A.rg + B.rg - Math.min(A.rg, B.lf);
			return res;
		}

		public void solve(InputReader in, PrintWriter out) {
			s = in.next();
			n = s.length();
			m = in.nextInt();
			seg = new node[4 * n + 80];
			for (int i = 1; i < 4 * n + 70; i++)
				seg[i] = new node(0, 0, 0);
			build(1, 0, n);
			for (int i = 0, l, r; i < m; i++) {
				l = in.nextInt();
				r = in.nextInt();
				out.println(get(l - 1, r, 1, 0, n).sq);
			}
		}
	}

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

    }
}

