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 static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
import static java.lang.System.out;
import java.math.*;
import java.util.*;
import java.io.*;

public class Main {
	static boolean LOCAL = System.getSecurityManager() == null;
	Scanner in = new Scanner(System.in);

	class Seg {
		int N;
		P[] ps;
		Seg(String str) {
			int n = str.length();
			N = Integer.highestOneBit(n) << 1;
			ps = new P[N * 2];
			for (int i = 0; i < n; i++) {
				if (str.charAt(i) == '(') ps[N + i] = new P(1, 0);
				else ps[N + i] = new P(0, 1);
			}
			for (int i = n; i < N; i++) ps[N + i] = new P(0, 0);
			for (int i = N - 1; i > 0; i--) {
				ps[i] = merge(ps[i * 2], ps[i * 2 + 1]);
			}
		}
		P query(int l, int r) {
			return range(1, l, r, 0, N);
		}
		P range(int o, int l, int r, int L, int R) {
			if (l <= L && R <= r) return ps[o];
			int M = (L + R) / 2;
			if (M >= r) return range(o * 2, l, r, L, M);
			if (M <= l) return range(o * 2 + 1, l, r, M, R);
			return merge(range(o * 2, l, M, L, M),
					range(o * 2 + 1, M, r, M, R));
		}
		P merge(P p, P q) {
			P r = new P(q.left, p.right);
			if (q.right > p.left) r.right += q.right - p.left;
			else r.left += p.left - q.right;
			return r;
		}
	}
	void run() {
		String str = in.next();
		int m = in.nextInt();
		Seg seg = new Seg(str);
		while (m-- != 0) {
			int l = in.nextInt() - 1, r = in.nextInt();
			P p = seg.query(l, r);
			out.println(r - l - p.left - p.right);
		}
	}
	class P {
		int left, right;

		public P(int left, int right) {
			super();
			this.left = left;
			this.right = right;
		}

		@Override
		public String toString() {
			return "[" + left + ", " + right + "]";
		}
		
	}
	
	void debug(Object... os) {
		System.err.println(deepToString(os));
	}

	public static void main(String[] args) {
		if (LOCAL) {
			try {
				System.setIn(new FileInputStream("./../../in"));
//				System.setOut(new PrintStream("./../../out"));
			} catch (Throwable e) {
				LOCAL = false;
			}
		}
		long start = 0;
		if (LOCAL)
			start = System.nanoTime();
		new Main().run();
		if (LOCAL)
			System.err.printf("[Time : %.6f]%n", (System.nanoTime() - start) * 1e-9);
	}
}

class Scanner {
	BufferedReader br;
	StringTokenizer st;

	Scanner(InputStream in) {
		br = new BufferedReader(new InputStreamReader(in));
		eat("");
	}

	void eat(String s) {
		st = new StringTokenizer(s);
	}

	String nextLine() {
		try {
			return br.readLine();
		} catch (IOException e) {
			return null;
		}
	}

	boolean hasNext() {
		while (!st.hasMoreTokens()) {
			String s = nextLine();
			if (s == null)
				return false;
			eat(s);
		}
		return true;
	}

	String next() {
		hasNext();
		return st.nextToken();
	}

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

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

	double nextDouble() {
		return Double.parseDouble(next());
	}
}