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


public class Main {
	public static void main(String[] args) throws Throwable {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		char[] arr = br.readLine().toCharArray();
		SegmentTree tree = new SegmentTree(arr);
		int m = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		while(m-->0)
		{
			StringTokenizer st = new StringTokenizer(br.readLine());
			int l = Integer.parseInt(st.nextToken())-1;
			int r = Integer.parseInt(st.nextToken())-1;
			sb.append(tree.search(l, r)+"\n");
		}
		System.out.println(sb);
	}
	static class SegmentTree
	{
		static class Node{
			int openNotClosed,closedNotOpen,ans;
			public Node()
			{
				openNotClosed = 0;
				closedNotOpen = 0;
				ans = 0;
			}
		}
		int n;
		char[] in;
		Node[] tree;
		public SegmentTree(char[] in)
		{
			this.in = in;
			int ind = 1;
			while(n<in.length)
			{
				n = 1<<ind++;
			}
			tree = new Node[n<<1];
			build(1,0,in.length-1);
		}
		private int left(int cur)
		{
			return cur<<1;
		}
		private int right(int cur)
		{
			return (cur<<1) + 1;
		}
		public void build(int cur,int l,int r)
		{
			if(l==r)
			{
				Node node = new Node();
				if(in[l]=='(')
					node.openNotClosed = 1;
				else
					node.closedNotOpen = 1;
				tree[cur] = node;
				return;
			}
			int left = left(cur);
			int right = right(cur);
			int mid = (l+r) >> 1;
			build(left, l, mid);
			build(right, mid+1, r);
			
			Node curNode = new Node();
			Node leftNode = tree[left];
			Node rightNode = tree[right];
			int ans = leftNode.ans + rightNode.ans + (Math.min(leftNode.openNotClosed,rightNode.closedNotOpen)<<1 );
			curNode.ans = ans;
			if(ans == leftNode.ans + rightNode.ans)
			{
				curNode.closedNotOpen = leftNode.closedNotOpen + rightNode.closedNotOpen;
				curNode.openNotClosed = leftNode.openNotClosed + rightNode.openNotClosed;
			}
			else
			{
				int taken = Math.min(leftNode.openNotClosed, rightNode.closedNotOpen);
				curNode.closedNotOpen = leftNode.closedNotOpen + (rightNode.closedNotOpen - taken);
				curNode.openNotClosed = rightNode.openNotClosed + (leftNode.openNotClosed - taken);
			}
			tree[cur] = curNode;
		}
		public int search(int lq,int rq)
		{
			return search(1, 0,in.length-1,lq,rq).ans;
		}
		public Node search(int cur,int l,int r,int lq,int rq)
		{
			if(r<lq || l>rq)
				return new Node();
			if(l==r)
			{
				return tree[cur];
			}
			if(l>=lq && r<=rq)
				return tree[cur];
			Node curNode = new Node();
			int mid = (l+r) >> 1;
			Node leftNode = search(left(cur),l,mid,lq,rq);
			Node rightNode= search(right(cur), mid+1, r, lq, rq);
			int ans = leftNode.ans + rightNode.ans + (Math.min(leftNode.openNotClosed,rightNode.closedNotOpen)<<1 );
			curNode.ans = ans;
			if(ans == leftNode.ans + rightNode.ans)
			{
				curNode.closedNotOpen = leftNode.closedNotOpen + rightNode.closedNotOpen;
				curNode.openNotClosed = leftNode.openNotClosed + rightNode.openNotClosed;
			}
			else
			{
				int taken = Math.min(leftNode.openNotClosed, rightNode.closedNotOpen);
				curNode.closedNotOpen = leftNode.closedNotOpen + (rightNode.closedNotOpen - taken);
				curNode.openNotClosed = rightNode.openNotClosed + (leftNode.openNotClosed - taken);
			}
			return curNode;
		}
	}
}