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

public class C380 {

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		String x = sc.next();
		int n = x.length();
		int N = 1;
		while (N < n)
			N <<= 1; // padding

		Pair[] in = new Pair[N + 1];
		
		for (int i = 1; i <= n; i++)
			in[i] = x.charAt(i - 1) == '(' ? new Pair(1,0) : new Pair(0,1);
		for (int i = n + 1; i < in.length; i++) {
			in[i] = null;
		}
		SegmentTree st = new SegmentTree(in);
		int m =sc.nextInt();
		while(m-->0) {
			pw.println(st.query(sc.nextInt(), sc.nextInt(),pw));
		}
		pw.flush();
		
		

	}

	public static Pair combine(Pair l, Pair r) {
		if(l==null)
			return r; 
		if(r==null)
			return l;
		int nc = l.c;
		int no = r.o;
		if (l.o > r.c)
			no += l.o - r.c;
		else if (r.c > l.o)
			nc += r.c - l.o;
		Pair n = new Pair(no, nc);
		return n;
	}

	static class Pair {
		int o, c;

		public Pair(int o, int c) {
			this.o = o;
			this.c = c;
		}

	}

	static class SegmentTree { 

		int N;  
		Pair[] array, sTree;

		SegmentTree(Pair[] in) {
			array = in;
			N = in.length - 1;
			sTree = new Pair[N << 1]; 
			
			build(1, 1, N);
		}

		void build(int node, int b, int e) 
		{
			if (b == e)
				sTree[node] = array[b];
			else {
				int mid = b + e >> 1;
				build(node << 1, b, mid);
				build(node << 1 | 1, mid + 1, e);
				sTree[node] = combine(sTree[node << 1] , sTree[node << 1 | 1]);
			}
		}

		

		int query(int i, int j,PrintWriter pw) {
			Pair p = query(1, 1, N, i, j);
			
			if(p==null)
				return 0;
			//pw.println(p.c + " "+ p.o);
			return j-i+1-p.c-p.o;
		}

		Pair query(int node, int b, int e, int i, int j) // O(log n)
		{
			if (i > e || j < b)
				return null;
			if (b >= i && e <= j)
				return sTree[node];
			int mid = b + e >> 1;
			
			Pair q1 = query(node << 1, b, mid, i, j);
			Pair q2 = query(node << 1 | 1, mid + 1, e, i, j);
			return combine(q1 , q2);

		}
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public Scanner(FileReader r) {
			br = new BufferedReader(r);
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

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

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

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

	}
}
