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

public class Main{

    BufferedReader in;
    StringTokenizer str = null;
    PrintWriter out;

    private String next() throws Exception{
    	while (str == null || !str.hasMoreElements())
    	    str = new StringTokenizer(in.readLine());
    	return str.nextToken();
    }
    
    private int nextInt() throws Exception{
	return Integer.parseInt(next());
    }
    
    public void run() throws Exception{
    	in = new BufferedReader(new InputStreamReader(System.in));
    	out = new PrintWriter(System.out);
	
	char []a = next().toCharArray();
	
	SegmentTree tree = new SegmentTree(a);
	
	int q = nextInt();
	for(int i=0;i<q;i++){
	    int l = nextInt()-1, r = nextInt()-1;
	    Node ans = tree.get(1, 0, a.length-1, l, r);
	    
	    out.println(2*ans.ans);
	}
	
        out.close();
    }
    
    static class SegmentTree{
	int n;
	Node []a;
	
	public SegmentTree(char []b){
	    this.n = b.length;
	    a = new Node[4*n];
	    build(1, 0, n-1, b);
	}
	
	private void build(int v, int tl, int tr, char []b){
	    if (tl == tr){
		a[v] = makeData(b[tl]);
		return;
	    }
	    
	    int tm = (tl + tr) >> 1;
	    build(2*v, tl, tm, b);
	    build(2*v+1, tm+1, tr, b);
	    
	    a[v] = merge(a[2*v], a[2*v+1]);
	}
	
	public Node get(int v, int tl, int tr, int l, int r){
	    if (l > r) return new Node(0, 0, 0);
	    if (tl == l && tr == r){
		return a[v];
	    }
	    
	    int tm = (tl + tr) >> 1;
	    
	    Node left = get(2*v, tl, tm, l, Math.min(tm, r));
	    Node right = get(2*v+1, tm+1, tr, Math.max(tm+1, l), r);
	    
	    return merge(left, right);
	}
	
	private Node merge(Node a, Node b){
	    int t = Math.min(a.right, b.left);
	    Node r = new Node(0, 0, 0);
	    r.ans = a.ans + b.ans + t;
	    r.left = a.left + b.left - t;
	    r.right = a.right + b.right - t;
	    
	    return r;
	}
	
	private Node makeData(char x){
	    Node r = new Node(0, 0, 0);
	    if (x == '(') r.right = 1;
	    if (x == ')') r.left = 1;
	    
	    return r;
	}
    }
    
    static class Node{
	int left, ans, right;
	public Node(int a, int b, int c){
	    this.left = a;
	    this.ans = b;
	    this.right = c;
	}
    }
    
    public static void main(String args[]) throws Exception{
	new Main().run();
    }
}