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.lang.String;
import java.util.Scanner;


public class C{
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter writer= new PrintWriter(System.out);
		try{
			String sequence = reader.readLine();
			Segment test = new Segment(sequence);
			test.build(0, 0, sequence.length());
			int m = Integer.parseInt(reader.readLine());
			for(int i = 0; i < m; i++){
				String[] strs = reader.readLine().split("\\s+");
				writer.println(test.querry(Integer.parseInt(strs[0]) - 1, 
						Integer.parseInt(strs[1])));
			}
			reader.close();
		}catch(IOException e){
			e.printStackTrace();
		}
		
		
		//writer.println(test);
		
		
		
		
		writer.flush();
		writer.close();
		

	}
}


final class Segment {
	
	char[] root;
	int[][] segment;
	
	public Segment(String sequence){
		root = sequence.toCharArray();
		segment = new int[root.length*4][];
		for(int i = 0; i < segment.length; i++){
			segment[i] = new int[3];
			segment[i][0] = segment[i][1] = segment[i][2] = 0;
		}
	}
	
	public void build(int id, int left, int right){
		if(right - left < 2){
			if(root[left] == '(') segment[id][1] = 1;
			else if(root[left] == ')') segment[id][2] = 1;
			return;
		}
		else{
			int mid = (left+right)/2;
			build(2*id + 1, left, mid);
			build(2*id + 2, mid, right);
			int tmp = Math.min(segment[2 * id + 1][1], segment[2 * id + 2][2]);
		    segment[id][0] = segment[2 * id + 1][0] + segment[2 * id + 2][0] + 2 * tmp;
		    segment[id][1] = segment[2 * id + 1][1] + segment[2 * id + 2][1] - tmp;
		    segment[id][2] = segment[2 * id + 1][2] + segment[2 * id + 2][2] - tmp;
		}
	}
	
	private int[] node(int x, int y, int id, int left, int right ){
		if(left >= y || x >= right) return new int[]{0,0,0};
		if(x <= left && right <= y){
			return segment[id];
		}
		int mid = (left + right)/2;
		int[] a = node(x, y, 2 * id + 1, left , mid);
		int[] b = node(x, y, 2 * id + 2, mid, right);
	    int T, temp, O, C;
	    temp = Math.min(a[1] , b[2]);
	    T = a[0] + b[0] + 2 * temp;
	    O = a[1] + b[1] - temp;
	    C = a[2] + b[2] - temp;
	    return new int[]{T, O, C};
	}
	
	public int querry(int left, int right){
		return node(left, right, 0, 0, root.length)[0];
	}
	
	@Override
	public String toString(){
		return new String(root);
	}

	

}
