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 opened;
		int closed;
		int total;
		public Node() {
		}
		public Node(int o, int c, int t) {
			opened = o;
			closed = c;
			total = t;
		}
	}
	static int N;
	static char[] arr;
	static Node[] sTree;
	
	static void build(int node, int b, int e)
	{
		if(b==e) sTree[node] = (arr[b]=='(')?new Node(1,0,0):(arr[b]==')')?new Node(0,1,0):new Node(0,0,0);
		else
		{
			build(node<<1,b,(b+e)/2);
			build((node<<1)+1,(b+e)/2+1,e);
			
			Node left = sTree[node<<1];
			Node right = sTree[(node<<1)+1];
			Node curr = new Node();
			if(left.opened > 0 && right.closed>0)
			{
				if(left.opened>=right.closed)
				{
					curr.total = (2*right.closed) + right.total + left.total;
					curr.closed = left.closed;
					curr.opened = (left.opened-right.closed) + right.opened;
				}
				else
				{
					curr.total = (2*left.opened) + right.total + left.total;
					curr.closed = (right.closed-left.opened) + left.closed;
					curr.opened = right.opened;
				}
			}
			else
			{
				curr.total = right.total + left.total;
				curr.closed = right.closed + left.closed;
				curr.opened = right.opened + left.opened;
			}
			sTree[node] = curr;
		}
	}
	
	static Node query(int i, int j)
	{
		return query(1,1,N,i,j);
	}
	
	static Node query(int node, int b, int e, int i, int j)
	{
		if(i>e || j <b)
			return new Node(0,0,0);	
		
		if(b>= i && e <= j)
			return sTree[node];
		
		Node q1 = query(node<<1,b,(b+e)/2,i,j);
		Node q2 = query((node<<1)+1,(b+e)/2+1,e,i,j);
		
		Node curr = new Node();
		if(q1.opened > 0 && q2.closed>0)
		{
			if(q1.opened>=q2.closed)
			{
				curr.total = (2*q2.closed) + q2.total + q1.total;
				curr.closed = q1.closed;
				curr.opened = (q1.opened-q2.closed) + q2.opened;
			}
			else
			{
				curr.total = (2*q1.opened) + q2.total + q1.total;
				curr.closed = (q2.closed-q1.opened) + q1.closed;
				curr.opened = q2.opened;
			}
		}
		else
		{
			curr.total = q2.total + q1.total;
			curr.closed = q2.closed + q1.closed;
			curr.opened = q2.opened + q1.opened;
		}
		return curr;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		String s = bf.readLine();
		int n = s.length();
		
		N = 1; while(N < n) N <<= 1; 
		arr = new char[N+1];
		
		for(int i = 0; i < s.length(); ++i)
			arr[i+1] = s.charAt(i);
			
		sTree = new Node[N<<1];
		build(1,1,N);
		
		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());
			
			Node c = query(i,j);
			out.println(c.total);
		}
		out.flush();
		out.close();
	}
}
















