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 «()(())(())».
//package Practise;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class R223qESerejaAndBrackets {

	static Node3 segtree[];
	static char a[];
	
	public static void main(String args[] ) throws Exception {
		   
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    PrintWriter w = new PrintWriter(System.out);
	    
	    a = br.readLine().toCharArray();
	    int n = a.length;      
	    
	    segtree = new Node3[4*n];
	    build(0,n-1,0);
	    
	    int m = ip(br.readLine());
	    for(int i=0;i<m;i++){
	    	StringTokenizer st2 = new StringTokenizer(br.readLine());
	    	int l = ip(st2.nextToken()) - 1;
	    	int r = ip(st2.nextToken()) - 1;
	    	w.println(find(0,n-1,0,l,r).ans);
	    }
	    
	    w.close(); 
	}
	
	public static void build(int s,int e,int c){
		if(s == e)
			segtree[c] = new Node3(0,a[s] == '(' ? 1 : 0,a[s] == ')' ? 1 : 0);
		else{
			int m = (s + e) / 2;
			build(s,m,2*c+1);
			build(m+1,e,2*c+2);
			segtree[c] = merge(segtree[2*c+1],segtree[2*c+2]);
		}
	}
	
	public static Node3 find(int s,int e,int c,int l,int r){
		if(s == l && e == r)
			return segtree[c];
		int m = (s + e) / 2;
		if(l <= m && r <= m)	return find(s,m,2*c+1,l,r);
		else if(l > m && r > m)	return find(m+1,e,2*c+2,l,r);
		else	return merge(find(s,m,2*c+1,l,m) , find(m+1,e,2*c+2,m+1,r));
	}
	
	public static Node3 merge(Node3 x,Node3 y){
		Node3 ret = new Node3(0,0,0);
		int r = Math.min(x.open,y.close);
		ret.ans = x.ans + y.ans + 2*r;
		ret.open = x.open + y.open - r;
		ret.close = x.close + y.close - r;
		return ret;
	}
	
	public static int ip(String s){
		return Integer.parseInt(s);
	}
}

class Node3{
	int ans,open,close;
	Node3(int a,int b,int c){
		ans = a;
		open = b;
		close = c;
	}
}
