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 C_380 {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		
		String s = sc.next();
		int n = s.length();
		int N = 1;
		while(N < n)
			N <<= 1;
		int[] array = new int[N + 1];
		for(int i = 1; i <= n; i++)
			array[i] = s.charAt(i - 1) == '(' ? 0 : 1;
		SegmentTree tree = new SegmentTree(array);
		
		int m = sc.nextInt();
		while(m-->0) {
			pw.println(2 * tree.query(sc.nextInt(), sc.nextInt()));
		}
		
		pw.flush();
	}
	
	public static class Tuple {
		int r, l, cr, cl;
		
		public Tuple(int r, int l, int cr, int cl) {
			this.r = r;
			this.l = l;
			this.cr = cl;
			this.cl = cl;
		}
	}
	
	public static class SegmentTree {
		
		int N;
		int[] in, l, r, cl, cr;
		
		public SegmentTree(int[] array) {
			in = array;
			N = array.length - 1;
			l = new int[N<<1];
			r = new int[N<<1];
			cl = new int[N<<1];
			cr = new int[N<<1];
			build(1, 1, N);
		}
		
		public void build(int node, int b, int e) {
			if(b == e) {
				if(in[b] == 0)
					r[node] = 1;
				else
					l[node] = 1;
				return;
			}
			
			int left = node<<1, right = node<<1|1;
			int mid = (b + e)>>1;
			
			build(left, b, mid);
			build(right, mid + 1, e);
			
			r[node] = r[left] + r[right];
			l[node] = l[left] + l[right];
			int min = Math.min(r[left] - cr[left], l[right] - cl[right]);
			cr[node] = cr[left] + cr[right] + min;
			cl[node] = cl[left] + cl[right] + min;
		}
		
		public int query(int l, int r) {
			Tuple t = query(1, 1, N, l, r);
			return Math.min(t.cl, t.cr);
		}
		
		public Tuple query(int node, int b, int e, int ll, int rr) {
			if(rr < b || ll > e)
				return new Tuple(0, 0, 0, 0);
			if(b >= ll && e <= rr)
				return new Tuple(r[node], l[node], cr[node], cl[node]);
			
			int left = node<<1, right = node<<1|1;
			int mid = (b + e)>>1;
						
			Tuple q1 = query(left, b, mid, ll, rr);
			Tuple q2 = query(right, mid + 1, e, ll, rr);
			Tuple ans = new Tuple(0, 0, 0, 0);
			
			ans.r = q1.r + q2.r;
			ans.l = q1.l + q2.l;
			int min = Math.min(q1.r - q1.cr, q2.l - q2.cl);
			ans.cr = q1.cr + q2.cr + min;
			ans.cl = q1.cl + q2.cl + min;
			
			return ans;
		}
		
		public void update_point(int n) {
			n += N - 1;
			int v = 1;
			if(l[n] == 1)
				v = 0;
			if(v == 0) {
				r[n] = 1;
				l[n] = 0;
			} else {
				r[n] = 0;
				l[n] = 1;
			}
			
			while(n > 1) {
				n /= 2;
				int left = n<<1, right = n<<1|1;
				r[n] = r[left] + r[right];
				l[n] = l[left] + l[right];
				int min = Math.min(r[left] - cr[left], l[right] - cl[right]);
				cr[n] = cr[left] + cr[right] + min;
				cl[n] = cl[left] + cl[right] + min;
			}
		}
	}

	public static class Scanner {
		StringTokenizer st;
		BufferedReader br;

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

		public Scanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}

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

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

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

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public char nextChar() throws IOException {
			return next().charAt(0);
		}

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

		public int[] nextIntArray(int n) throws IOException {
			int[] array = new int[n];
			for (int i = 0; i < n; i++)
				array[i] = nextInt();
			return array;
		}

		public Integer[] nextIntegerArray(int n) throws IOException {
			Integer[] array = new Integer[n];
			for (int i = 0; i < n; i++)
				array[i] = new Integer(nextInt());
			return array;
		}

		public long[] nextLongArray(int n) throws IOException {
			long[] array = new long[n];
			for (int i = 0; i < n; i++)
				array[i] = nextLong();
			return array;
		}

		public double[] nextDoubleArray(int n) throws IOException {
			double[] array = new double[n];
			for (int i = 0; i < n; i++)
				array[i] = nextDouble();
			return array;
		}

		public static int[] shuffle(int[] a) {
			int n = a.length;
			Random rand = new Random();
			for (int i = 0; i < n; i++) {
				int tmpIdx = rand.nextInt(n);
				int tmp = a[i];
				a[i] = a[tmpIdx];
				a[tmpIdx] = tmp;
			}
			return a;
		}

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

		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
}
