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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

/**
 * TLE on test 13
 * Can't not figure out why?
 * 
 * @since 2014.03.16
 * @author whimsy
 *
 */
public class P380C {
	static class Tree {
		Node root;
		String data;

		public Tree(String data2) {
			data = data2;
			root = buildTree(1, data.length());
		}

		private Node buildTree(int l, int r) {
			Node ret = new Node();
			ret.l = l;
			ret.r = r;
			if (l == r) {
				ret.lv += data.charAt(l - 1) == '(' ? 1 : 0;
				ret.rv += data.charAt(l - 1) == ')' ? 1 : 0;
			} else {
				ret.left = buildTree(l, ret.mid());
				ret.right = buildTree(ret.mid() + 1, r);
				int t = Math.min(ret.left.lv, ret.right.rv);
				ret.v = ret.left.v + ret.right.v + t;
				ret.lv = ret.left.lv + ret.right.lv - t;
				ret.rv = ret.left.rv + ret.right.rv - t;
			}

			return ret;
		}

		public int retrieve(int l, int r) {
			return retrieve(root, l, r).v;
		}

		private Entry retrieve(Node x, int l, int r) {
			if (l <= x.l && r >= x.r)
				return new Entry(x);
			if (r <= x.mid())
				return retrieve(x.left, l, r);
			if (l > x.mid())
				return retrieve(x.right, l, r);
			Entry le = retrieve(x.left, l, x.mid());
			Entry re = retrieve(x.right, x.mid() + 1, r);
			int t = Math.min(le.lv, re.rv);
			return new Entry(le.v + re.v + t, le.lv + re.lv - t, re.rv + le.rv
					- t);
		}
	}

	static class Entry {
		int v, lv, rv;

		public Entry(Node x) {
			this.v = x.v;
			this.lv = x.lv;
			this.rv = x.rv;
		}

		public Entry(int v, int lv, int rv) {
			this.v = v;
			this.lv = lv;
			this.rv = rv;
		}
		@Override
		public String toString() {

			return v+" "+lv+" "+rv;
		}

	}

	static class Node {
		int v, lv, rv;
		int l, r;
		Node left, right;

		public Node() {
			v = lv = rv = l = r = 0;
			left = right = null;
		}

		public int mid() {
			return (l + r) / 2;
		}
		@Override
		public String toString() {
			return v+" "+lv+" "+rv+" | "+l + " "+r;
		}
	}

	private void solve() {
		InputReader in = new InputReader(System.in);
		PrintWriter out = new PrintWriter(System.out);
		String data = in.nextLine();
		
		int n = in.parseInt1D(1)[0];
		Tree tree = new Tree(data);
		for (int i = 0; i < n; ++i) {
			int [] tmp = in.parseInt1D(2);
			int l = tmp[0];
			int r = tmp[1];
			out.println(tree.retrieve(l, r)*2);
		}
		out.flush();
		out.close();
	}

	public static void main(String[] args) {
		new P380C().solve();
	}


	static class InputReader {
		private BufferedReader br;
		private StringTokenizer st;

		public InputReader(InputStream in) {
			br = new BufferedReader(new InputStreamReader(in));
			
		}

		public void readLine() {
			try {
				st = new StringTokenizer(br.readLine());
			} catch (IOException e) {
				return;
			}
		}

		public int nextInt() {
			return Integer.parseInt(st.nextToken());
		}
		public int[] parseInt1D(int n) {
			readLine();
			int r[] = new int[n];
			for (int i = 0; i < n; i++) {
				r[i] = nextInt();
			}
			return r;
		}
		public String nextLine(){
			readLine();
			return st.nextToken();
			
		}

	}
}
