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 «()(())(())».

// Problem: C. Sereja and Brackets
// Contest: Codeforces - Codeforces Round #223 (Div. 1)
// URL: https://codeforces.com/contest/380/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

import java.io.*;
import java.util.*;

public class Main {
    private static PrintWriter pw = new PrintWriter(System.out);
    private static InputReader sc = new InputReader();

    static class InputReader{
        private static BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        private static StringTokenizer tk;

        private void next()throws IOException{
            if(tk == null || !tk.hasMoreTokens())   
                tk = new StringTokenizer(r.readLine());
        }

        private int nextInt()throws IOException{
            next();
            return Integer.parseInt(tk.nextToken());
        }

        private String readString()throws IOException{
            next();
            return tk.nextToken();
        }
    }

    public static void main(String args[])throws IOException{
        int t = 1;
        while(t-->0)    solve();
        pw.flush();
        pw.close();
    }
    
    private static char c[];
    private final static int open = 1, close = 2, complete = 0;
    
    static class Node{
    	int begin, end, data[];
    	Node left, right;
    	
    	Node(int b, int e){
    		begin = b;
    		end = e;
    		data = new int[3];
    		
    		if(begin != end){
    			int mid = (begin + end)/2;
    			
    			left = new Node(begin, mid);
    			right = new Node(mid+1, end);
    			
    			int tmp = Math.min(left.data[open], right.data[close]);
    			
    			data[complete] = left.data[complete] + right.data[complete] + 2*tmp;
    			data[open] = left.data[open] + right.data[open] - tmp;
    			data[close] = left.data[close] + right.data[close] - tmp;
    		}
    		else{
    			if(c[begin] == '(')
    				data[open] = 1;
    			else
    				data[close] = 1;
    		}
    	} 
    	
    	int[] query(int l, int r){
    		if(l > r || begin > r || l > end)
    			return new int[3];
    			
    		if(l <= begin && end <= r)
    			return data;
    			
    		int[] p = left.query(l, r), q = right.query(l, r), ans = new int[3];
    		
    		int temp = Math.min(p[open], q[close]);
    		ans[complete] = p[complete] + q[complete] + 2*temp;
    		ans[open] = p[open] + q[open] - temp;
    		ans[close] = p[close] + q[close] - temp;
    		
    		return ans;
    	}
    }

    private static void solve()throws IOException{
		c = sc.readString().toCharArray();
		
		int n = c.length;
		Node root = new Node(0, n-1);
		
		int q = sc.nextInt();
		while(q-->0){
			int l = sc.nextInt() - 1, r = sc.nextInt() - 1;
			
			pw.println(+root.query(l, r)[0]);
		}
    }
}