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

public class Main {

	public static void main(String args[]) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		char[] a = br.readLine().toCharArray();
		int n = a.length;
		int N = 1;
		while (N < n)
			N <<= 1;
		pair[] in = new pair[N + 1];
		Arrays.fill(in, new pair(-1, -1));
		for (int i = 0; i < n; i++) {
			in[i + 1] = new pair(a[i] == '(' ? 1 : 0, a[i] == ')' ? 1 : 0);
		}
		SegmentTree sg = new SegmentTree(in);
		int q = Integer.parseInt(br.readLine());
		while (q-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			pw.println(sg.query(x, y));
		}
		pw.flush();
	}

	static class SegmentTree { // 1-based DS, OOP

		int N; // the number of elements in the array as a power of 2 (i.e. after padding)
		pair[] array, sTree, lazy;

		SegmentTree(pair[] in) {
			array = in;
			N = in.length - 1;
			sTree = new pair[N << 1]; // no. of nodes = 2*N - 1, we add one to cross out index zero
			lazy = new pair[N << 1];
			build(1, 1, N);
		}

		void build(int node, int b, int e) // O(n)
		{
			if (b == e)
				sTree[node] = array[b];
			else {
				int mid = b + e >> 1;
				build(node << 1, b, mid);
				build(node << 1 | 1, mid + 1, e);
				int x = sTree[node << 1 | 1].x;
				int y = sTree[node << 1].y;
				if (x == -1)
					sTree[node] = sTree[node << 1];
				else if (y == -1)
					sTree[node] = sTree[node << 1 | 1];
				else {
					if (sTree[node << 1].x >= sTree[node << 1 | 1].y)
						x += sTree[node << 1].x - sTree[node << 1 | 1].y;
					else
						y += sTree[node << 1 | 1].y - sTree[node << 1].x;
					sTree[node] = new pair(x, y);
				}
			}
		}

//		void update_point(int index, long val) // O(log n)
//		{
//			index += N - 1;
//			sTree[index] = val;
//			while (index > 1) {
//				index >>= 1;
//				sTree[index] = Math.max(sTree[index << 1], sTree[index << 1 | 1]);
//			}
//		}
//
//		void update_range(int i, int j, int val) // O(log n)
//		{
//			update_range(1, 1, N, i, j, val);
//		}
//
//		void update_range(int node, int b, int e, int i, int j, int val) {
//			if (i > e || j < b)
//				return;
//			if (b >= i && e <= j) {
//				sTree[node] = (e - b + 1) * val;
//				lazy[node] = val;
//			} else {
//				int mid = b + e >> 1;
//				propagate(node, b, mid, e);
//				update_range(node << 1, b, mid, i, j, val);
//				update_range(node << 1 | 1, mid + 1, e, i, j, val);
//				sTree[node] = sTree[node << 1] + sTree[node << 1 | 1];
//			}
//
//		}
//
//		void propagate(int node, int b, int mid, int e) {
//			lazy[node << 1] += lazy[node];
//			lazy[node << 1 | 1] += lazy[node];
//			sTree[node << 1] += (mid - b + 1) * lazy[node];
//			sTree[node << 1 | 1] += (e - mid) * lazy[node];
//			lazy[node] = 0;
//
//		}

		int query(int i, int j) {
			pair t = query(1, 1, N, i, j);
			return j - i + 1 - t.x - t.y;
		}

		pair query(int node, int b, int e, int i, int j) // O(log n)
		{
			if (i > e || j < b)
				return new pair(-1, -1);
			if (b >= i && e <= j)
				return sTree[node];
			int mid = b + e >> 1;
//			propagate(node, b, mid, e);
			pair q1 = query(node << 1, b, mid, i, j);
			pair q2 = query(node << 1 | 1, mid + 1, e, i, j);
			if (q1.x == -1)
				return q2;
			else if (q2.x == -1)
				return q1;
			int x = q2.x;
			int y = q1.y;
			if (q1.x >= q2.y)
				x += q1.x - q2.y;
			else
				y += q2.y - q1.x;
			return new pair(x, y);

		}

	}

	static class pair implements Comparable<pair> {
		int x;
		int y;

		public pair(int a, int b) {
			x = a;
			y = b;
		}

		@Override
		public int compareTo(pair o) {
			return x - o.x;
		}

	}
}
 	 	      		  		 	 	 						 			