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

public class E
{
	private static Node [] nodes;

	public static void main(String [] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));

		char [] str = reader.readLine().toCharArray();
		int n = str.length;

		nodes = new Node[n];
		Node root = makeTree(0, n-1, null);

		for(int i = 0 ; i < n ; i++)
		{
			nodes[i].maxLen = 0;
			nodes[i].leftUnused = str[i] == '(' ? 1 : 0;
			nodes[i].rightUnused = 1-nodes[i].leftUnused;
		}

		root.set();


		int queryNumber = Integer.parseInt(reader.readLine());

		while(queryNumber-- > 0)
		{
			StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
			int left = Integer.parseInt(tokenizer.nextToken()) - 1;
			int right = Integer.parseInt(tokenizer.nextToken()) - 1;

			writer.println(root.get(left, right)[0]);
		}

		writer.flush();
		writer.close();
	}

	private static Node makeTree(int from, int to, Node parent)
	{
		if(from == to)
			return nodes[from] = new Node(from, to, parent);

		Node res = new Node(from, to, parent);
		res.left = makeTree(from, (from+to)/2, res);
		res.right = makeTree((from+to)/2+1, to, res);

		return res;

	}

	static class Node
	{
		int maxLen, leftUnused, rightUnused;

		int from, to;
		Node left, right, parent;

		public Node(int from, int to, Node parent)
		{
			this.from = from;
			this.to = to;
			this.parent = parent;
		}

		public void set()
		{
			if(left == null)
			{
				return;
			}
			else
			{
				left.set();
				right.set();
				int toUse = Math.min(left.leftUnused, right.rightUnused);
				maxLen = left.maxLen + right.maxLen + 2*toUse;
				leftUnused = left.leftUnused + right.leftUnused - toUse;
				rightUnused = left.rightUnused + right.rightUnused - toUse;
			}
		}

		public int[] get(int a, int b)
		{
			if(from >= a && to <= b)
				return new int[]{maxLen, leftUnused, rightUnused};
			else if(from > b || to < a)
				return new int[3];
			else
			{
				int [] x = left.get(a, b);
				int [] y = right.get(a, b);

				int [] res = new int[3];
				int toUse = Math.min(x[1], y[2]);
				res[0] = x[0] + y[0] + 2*toUse;
				res[1] = x[1] + y[1] - toUse;
				res[2] = x[2] + y[2] - toUse;

				return res;

			}
		}
	}
}
