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


public class Main {
	static BufferedReader in;
	static PrintWriter out;
	static StringTokenizer tok;
	
	static Node[] a;
	static int start;
	
	static void solve() throws Exception {
		char[] s = next().toCharArray();
		int n = s.length;
		a = new Node[4*n];
		for (start = 1; start < n; start *= 2);
		for (int i = 0; i < n; i++) {
			if (s[i] == '(') {
				a[start + i] = new Node(0, 1, 0);
			} else {
				a[start + i] = new Node(0, 0, 1);
			}
		}
 		for (int i = start+n; i <= 2*start; i++) {
 			a[i] = new Node(0, 0, 0);
 		}
		for (int i = start-1; i >= 1; i--) {
			a[i] = f(a[i*2], a[i*2+1]);
		}
		int q = nextInt();
		for (int i = 0; i < q; i++) {
			out.println(get(nextInt(), nextInt()));
		}
	}
	
	static class Node {
		int res, opened, closed;
		
		Node(int res, int opened, int closed) {
			this.res = res;
			this.opened = opened;
			this.closed = closed;
		}
	}

	static Node f(Node a, Node b) {
		int minV = Math.min(a.opened, b.closed);
		return new Node(a.res + b.res + 2*minV, a.opened + b.opened - minV, a.closed + b.closed - minV);
	}
	
	static int get(int l, int r) {
		Node resL = new Node(0, 0, 0);
		Node resR = new Node(0, 0, 0);
		l += start-1;
		r += start-1;
		while (l <= r) {
			if (l % 2 != 0) {
				resL = f(resL, a[l++]);
			}
			if (r % 2 == 0) {
				resR = f(a[r--], resR);
			}
			l /= 2;
			r /= 2;
		}		
		return f(resL, resR).res;
	}

	static int sqr(int x) {
		return x*x;
	}
	
	static int nextInt() throws IOException {
		return Integer.parseInt(next());
	}

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

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

	static BigInteger nextBigInteger() throws IOException {
		return new BigInteger(next());
	}
	
	static String next() throws IOException {
		while (tok == null || !tok.hasMoreTokens()) {
			tok = new StringTokenizer(in.readLine());
		}
		return tok.nextToken();
	}
	
	static String nextLine() throws IOException {
		tok = new StringTokenizer("");
		return in.readLine();
	}

	static boolean hasNext() throws IOException {
		while (tok == null || !tok.hasMoreTokens()) {
			String s = in.readLine();
			if (s == null) {
				return false;
			}
			tok = new StringTokenizer(s);
		}
		return true;
	}

	public static void main(String args[]) {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(new OutputStreamWriter(System.out));
			//in = new BufferedReader(new FileReader("input.in"));
			//out = new PrintWriter(new FileWriter("output.out"));
			solve();
			in.close();
			out.close();
		} catch (Throwable e) {
			e.printStackTrace();
			java.lang.System.exit(1);
		}
	}
}