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.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

public class E {
	private static int OFFSET=2;
	private static int tree[];
	public static void main(String[] args) throws Exception{
		Scanner sc = new Scanner(System.in);
		String s = readString();
		int[] A = new int[s.length()+1];
		int offset = 1;
		while(OFFSET < s.length()+2){
			OFFSET*=2;
		}
		tree = new int[2*OFFSET+1];
		int[] l = new int[s.length()+1];
		int[] r = new int[s.length()+1];
		for(int i = 1; i <= s.length(); i++){
			if(s.charAt(i-1) == '('){
				A[i] = A[i-1] + 1;
				l[i] = l[i-1] + 1;
				r[i] = r[i-1];
			}
			else{
				A[i] = A[i-1] - 1;
				l[i] = l[i-1];
				r[i] = r[i-1] + 1;
			}
			update(i, A[i]);
		}
		int n = readInt();
		for(int i = 0; i < n; i++){
			int a = readInt();
			int b = readInt();
			int off = query(a, b);
			off = off - A[a-1];
			int best = 0;
			if(off < 0){
				best = Math.min(r[b]-r[a-1] + off, l[b]-l[a-1]);
			}
			else{
				best = r[b]-r[a-1];
			}
			System.out.println(2*best);
		}
		
			
	}
	
	private static void update(int i, int v){
		i += OFFSET;
		tree[i] = v;
		i /= 2;
		while(i > 0){
			tree[i] = Math.min(tree[2*i], tree[2*i+1]);
			i/=2;
		}
	}
	public static int query(int l, int r){
		int result = Integer.MAX_VALUE;
		l+= OFFSET -1;
		r+= OFFSET +1;
		while(l/2 != r/2){
			if(l%2 == 0){
				result = Math.min(result, tree[l^1]);
			}
			if(r%2 == 1){
				result = Math.min(result, tree[r^1]);
			}
			l/=2;
			r/=2;
		}
		return result;
	}
	
	static BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st = new StringTokenizer(" ");
	static String readString() throws Exception{
		while(!st.hasMoreTokens()){
			st = new StringTokenizer(stdin.readLine());
		}
		return st.nextToken();
	}
	static int readInt() throws Exception {
		return Integer.parseInt(readString());
	}
}
