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

public class SerejaAndBrackets {

	static class Node {
		int best, open, closed;

		public Node(int i, int j, int k) {
			best = i;
			open = j;
			closed = k;
		}
	}

	static class SegmentTree {

		Node tree[];
		int n;
		char c[];

		public SegmentTree(char cc[]) {
			computeN(cc.length);
			tree = new Node[n];
			c = cc;
			build();
		}

		void build() {
			build(1, 1, n / 2);
		}

		void build(int node, int l, int r) {
			if (node >= n || node < 1 || r < l || l < 1 || r > n / 2)
				return;
			if (l == r) {
				if (l > c.length)
					tree[node] = new Node(0, 0, 0);
				else
					tree[node] = (c[l - 1] == '(') ? new Node(0, 1, 0) : new Node(0, 0, 1);
				return;
			}
			int mid = (l + r) >> 1;
			int left = node << 1;
			int right = left | 1;
			build(left, l, mid);
			build(right, mid + 1, r);
			tree[node] = merge(left, right);
		}

		Node merge(int l, int r) {
			Node left = l < n ? tree[l] : new Node(0, 0, 0);
			Node right = r < n ? tree[r] : new Node(0, 0, 0);
			int add = Math.min(left.open, right.closed);
			return new Node(left.best + right.best + 2 * add, left.open + right.open - add,
					left.closed + right.closed - add);
		}
		
		Node query(int i, int j) {
			return query(1, 1, n / 2, i, j);
		}
		
		Node query(int node, int l, int r, int i, int j) {
			if (node > n || node < 1 || r < l || l < 1 || r > n / 2 || r < i || l > j)
				return new Node(0, 0, 0);
			if (l >= i && r <= j)
				return tree[node];
			int mid = (l + r) >> 1;
			int left = node << 1;
			int right = left | 1;
			Node lf = query(left, l, mid, i, j);
			Node ri = query(right, mid + 1, r, i , j);
			return mergeNodes(lf, ri);
		}
		
		Node mergeNodes(Node left, Node right) {
			int add = Math.min(left.open, right.closed);
			return new Node(left.best + right.best + 2 * add, left.open + right.open - add,
					left.closed + right.closed - add);
		}

		void computeN(int x) {
			n = 1;
			while (n < x)
				n <<= 1;
			n <<= 1;
		}
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		StringBuilder out2 = new StringBuilder();
		char s[] = bf.readLine().toCharArray();
		SegmentTree seg = new SegmentTree(s);
		int q = Integer.parseInt(bf.readLine());
		while (q-- > 0) {
			StringTokenizer st = new StringTokenizer(bf.readLine());
			int i = Integer.parseInt(st.nextToken());
			int j = Integer.parseInt(st.nextToken());
			out2.append(seg.query(i, j).best);
			out2.append("\n");
		}
		out.println(out2);
		out.flush();
		out.close();
	}
}
