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.StringTokenizer;

public class Main {
	public static int N, Q;
	public static String str;
	public static node[] nodes;

	public static void main(String[] args) throws IOException {
		BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
		str = f.readLine();
		N = str.length();
		nodes = new node[(N + 2) << 2 | 1];
		build();
		Q = Integer.parseInt(f.readLine());
		StringBuilder sb = new StringBuilder();
		for (; Q > 0; Q--) {
			StringTokenizer st = new StringTokenizer(f.readLine());
			int l = Integer.parseInt(st.nextToken());
			int r = Integer.parseInt(st.nextToken());
			sb.append(query(l, r).a * 2).append("\n");
		}
		System.out.print(sb.toString());
	}

	public static void build() {
		build(1, N, 1);
	}

	public static node query(int left, int right) {
		return query(left, right, 1, N, 1);
	}

	public static void build(int l, int r, int index) {
		nodes[index] = new node();
		if (l == r) {
			if (str.charAt(l - 1) == '(')
				nodes[index].b = 1;
			else
				nodes[index].c = 1;
			return;
		}
		int m = (l + r) >> 1;
		build(l, m, index << 1);
		build(m + 1, r, index << 1 | 1);
		pushUp(index);
	}

	public static node query(int L, int R, int l, int r, int index) {
		if (L <= l && r <= R) {
			return nodes[index];
		}
		int m = (l + r) >> 1;
		node res1 = new node();
		node res2 = new node();
		if (L <= m) {
			res1 = query(L, R, l, m, index << 1);
		}
		if (R > m) {
			res2 = query(L, R, m + 1, r, index << 1 | 1);
		}
		node res = new node();
		int X = Math.min(res1.b, res2.c);
		res.a = res1.a + res2.a + X;
		res.b = res1.b + res2.b - X;
		res.c = res1.c + res2.c - X;
		return res;
	}

	public static void pushUp(int index) {
		int X = Math.min(nodes[index << 1].b, nodes[index << 1 | 1].c);
		nodes[index].a = nodes[index << 1].a + nodes[index << 1 | 1].a + X;
		nodes[index].b = nodes[index << 1].b + nodes[index << 1 | 1].b - X;
		nodes[index].c = nodes[index << 1].c + nodes[index << 1 | 1].c - X;
	}
}

class node {
	public int a, b, c;

	public String toString() {
		return a + " " + b + " " + c;
	}
}