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 «()(())(())».
// In The Name of Allah

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




public class template{
	public static void main(String[] args) {
	InputStream inputStream = System.in;

    OutputStream outputStream = System.out;

    InputReader scan = new InputReader(inputStream);

    PrintWriter out = new PrintWriter(outputStream);
		String s = scan.next();
		char [] inp = s.toCharArray();
		segment_tree seg = new segment_tree(inp);
		int q = scan.nextInt();
		for (int i=0;i<q ;i++ ) {
			out.println(2*seg.query(scan.nextInt()-1,scan.nextInt()).ans);
		}
		out.close();
	}

static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }

}


class node{
	int open,close,ans;
	node(int open,int close,int ans){
		this.open = open;
		this.close = close;
		this.ans = ans;
	}

	@Override
	public  String toString(){
		return (this.open+"/"+this.close+"/"+this.ans);
	}
}

interface SegmentTree{
	public void build(int id,int l,int r);
	public node query(int id,int x,int y,int L,int R);
}

class segment_tree implements SegmentTree{
	public int MAXN = 100005;
	public int N;
	char [] input;
	node [] seg ;

	segment_tree(char[] input){
		this.input = input;
		this.N = input.length;
		seg = new node[4 * this.N];
		build(1,0,N);
		// for (int i=0;i<4*N;i++ ) {
		// 	System.out.print(seg[i]+"__");
		// }
	}

	public void build(int id, int l, int r){
		// System.out.println(id+"["+l+","+r+"]");
		if (r-l<2) {
			int open = 0,close = 0;
			if (input[l]=='(') {
				open = 1;
			}
			else{
				close = 1;
			}
			seg[id] = new node(open,close,0);
			return;
		}
		else{
			int mid = (l+r)/2;
			build(2*id,l,mid);
			build(2*id+1,mid,r);
			node cur1 = seg[2*id];
			node cur2 = seg[2*id+1];
			int tem = Math.min(cur1.open,cur2.close);
			int compelet = cur1.ans + cur2.ans + tem;
			int n_open = cur1.open + cur2.open - tem;
			int n_close =  cur1.close + cur2.close - tem;
			seg[id] = new node(n_open,n_close,compelet);
		}
	}

	public node query(int l,int r){
		return query(1,0,N,l,r);
	}

	public node query(int id, int x, int y, int L, int R){
		// System.out.println(id+"["+x+","+y+"]");
		if (x>=R || y<=L) {
			return new node(0,0,0);
		}
		else if (L<= x && y<=R){
			return seg[id];
		}
		else{
			int mid = (x+y)/2;
			node l = query(2*id,x,mid,L,R);
			node r = query(2*id+1,mid,y,L,R);
			int tmp = Math.min(l.open,r.close);
			return new node(l.open+r.open-tmp, l.close+r.close-tmp, l.ans + r.ans + tmp);
		}
	}



}






class pair implements Comparable{
	int _f;
	long _s;
	pair(int f,long s){
		_f = f;
		_s = s;
	}

	public int compareTo(Object o){
		pair s = (pair)o;
		if (s._f==this._f) {
			return Long.compare(this._s,s._s);
		}
		else{
			return Integer.compare(this._f,s._f);
		}
	}

	int first(){
		return _f;
	}

	long second(){
		return _s;
	}

	public String toString(){
		return "("+_f+" , " + _s +")";
	}

}

