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 file {
	static long mod = (long) Math.pow(10, 9) + 7;
	static Node[] stree;

	public static void main(String[] args) throws Exception {

		Scan scn = new Scan();
		Print printer = new Print();

		String str = scn.scanString();
		int q = scn.scanInt();
		stree = new Node[str.length() * 4 + 10];
		build(1, 0, str.length() - 1, str.toCharArray());
		// egiuehijnrgiuhrfjvnesrgh
		while (q-- > 0) {
			int l = scn.scanInt() - 1;
			int r = scn.scanInt() - 1;
			printer.printLine(query(1, 0, str.length() - 1, l, r).pair + "");
			
		}
		printer.close();
	}

	public static class Node {
		int open;
		int close;
		int pair;
	}

	public static Node combine(Node one, Node two) {
		int temp = Math.min(one.open, two.close);
		Node node = new Node();
		node.pair = one.pair + two.pair + temp * 2;
		node.open = one.open + two.open - temp;
		node.close = one.close + two.close - temp;
		return node;
	}

	public static Node build(int curr, int start, int end, char[] arr) {
		if (start == end) {
			Node node = new Node();
			node.open = arr[start] == '(' ? 1 : 0;
			node.close = arr[start] == ')' ? 1 : 0;
			stree[curr] = node;
			return node;
		}

		int mid = (start + end) >> 1;
		Node one = build(2 * curr, start, mid, arr);
		Node two = build(2 * curr + 1, mid + 1, end, arr);
		stree[curr] = combine(one, two);
		return stree[curr];

	}

	public static Node query(int node, int start, int end, int l, int r) {

		if (l > end || r < start)
			return new Node();

		if (l <= start && r >= end)
			return stree[node];

		int mid = (start + end) / 2;
		Node one = query(2 * node, start, mid, l, r);
		Node two = query(2 * node + 1, mid + 1, end, l, r);
		return combine(one, two);
	}

	static class Scan {
		private InputStream in;
		private byte[] buf = new byte[1024 * 1024];
		private int index;
		private int total;

		public Scan() {
			in = System.in;
			// try {
			// in = new FileInputStream(new File("/home/ujjwal/test/test"));
			// } catch (Exception ex) {
			//
			// }
		}

		public int scan() throws IOException {
			if (total < 0)
				throw new InputMismatchException();
			if (index >= total) {
				index = 0;
				total = in.read(buf);
				if (total <= 0)
					return -1;
			}
			return buf[index++];
		}

		public int scanInt() throws IOException {
			int integer = 0;
			int n = scan();
			while (isWhiteSpace(n))
				n = scan();
			int neg = 1;
			if (n == '-') {
				neg = -1;
				n = scan();
			}
			while (!isWhiteSpace(n)) {
				if (n >= '0' && n <= '9') {
					integer *= 10;
					integer += n - '0';
					n = scan();
				} else
					throw new InputMismatchException();
			}
			return neg * integer;
		}

		public long scanLong() throws IOException {
			long integer = 0;
			int n = scan();
			while (isWhiteSpace(n))
				n = scan();
			int neg = 1;
			if (n == '-') {
				neg = -1;
				n = scan();
			}
			while (!isWhiteSpace(n)) {
				if (n >= '0' && n <= '9') {
					integer *= 10;
					integer += n - '0';
					n = scan();
				} else
					throw new InputMismatchException();
			}
			return neg * integer;
		}

		public double scanDouble() throws IOException {
			double doub = 0;
			int n = scan();
			while (isWhiteSpace(n))
				n = scan();
			int neg = 1;
			if (n == '-') {
				neg = -1;
				n = scan();
			}
			while (!isWhiteSpace(n) && n != '.') {
				if (n >= '0' && n <= '9') {
					doub *= 10;
					doub += n - '0';
					n = scan();
				} else
					throw new InputMismatchException();
			}
			if (n == '.') {
				n = scan();
				double temp = 1;
				while (!isWhiteSpace(n)) {
					if (n >= '0' && n <= '9') {
						temp /= 10;
						doub += (n - '0') * temp;
						n = scan();
					} else
						throw new InputMismatchException();
				}
			}
			return doub * neg;
		}

		public String scanString() throws IOException {
			StringBuilder sb = new StringBuilder();
			int n = scan();
			while (isWhiteSpace(n))
				n = scan();
			while (!isWhiteSpace(n)) {
				sb.append((char) n);
				n = scan();
			}
			return sb.toString();
		}

		private boolean isWhiteSpace(int n) {
			if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1)
				return true;
			return false;
		}
	}

	static class Print {
		private final BufferedWriter bw;

		public Print() {
			bw = new BufferedWriter(new OutputStreamWriter(System.out));
		}

		public void print(String str) throws IOException {
			bw.append(str);
		}

		public void printLine(String str) throws IOException {
			print(str);
			bw.append("\n");
		}

		public void close() throws IOException {
			bw.close();
		}
	}

}

