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


public class A {

	static final int INF = (int)1e9;
	
	public static void main(String[] args) throws IOException 
	{
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		
		char[] s = sc.next().toCharArray();
		int n = 1;
		while(n < s.length) n <<= 1;
		int[] prefix = new int[n + 1];
		Arrays.fill(prefix, INF);
		prefix[0] = 0;
		for(int i = 1; i <= s.length; ++i)
			prefix[i] = prefix[i-1] + (s[i-1] == '(' ? 1 : -1);
		SegmentTree st = new SegmentTree(prefix);
		
		int q = sc.nextInt();
		while(q-->0)
		{
			int l = sc.nextInt(), r = sc.nextInt();
			int offset = prefix[l-1];
			st.update(l, r, -offset);
			
			int extraClose = Math.max(-st.query(l, r), 0);
			int extraOpen = extraClose + st.query(r, r);
			out.println(r - l + 1 - (extraClose + extraOpen));
			st.update(l, r, offset);
		}
		out.flush();
		out.close();
	}
	
	static class SegmentTree
	{
		int[] array, sTree, lazy;
		int N;
		
		SegmentTree(int[] in)
		{
			N = in.length - 1;
			sTree = new int[N<<1];
			lazy = new int[N<<1];
			array = in;
			build(1, 1, N);
		}
		
		void build(int node, int b, int e)
		{
			if(b == e)
			{	
				sTree[node] = array[b];
				return;
			}
			build(node<<1, b, (b+e) / 2);
			build((node<<1) + 1, (b+e) / 2 + 1, e);
			sTree[node] = Math.min(sTree[node<<1], sTree[(node<<1) + 1]);
		}
		
		void update(int l, int r, int val)
		{
			update(1, 1, N, l, r, val);
		}
		
		void update(int node, int b, int e, int l, int r, int val)
		{
			if(r < b || e < l)
				return;
			if(l <= b && e <= r)
			{
				lazy[node] += val;
				sTree[node] += val;
				return;
			}
			propagate(node, b, e);
			update(node<<1, b, (b+e) / 2, l, r, val);
			update((node<<1) + 1, (b+e) / 2 + 1, e, l, r, val);
		}
		
		void propagate(int node, int b, int e)
		{
			if(lazy[node] == 0)
				return;
			int val = lazy[node];
			lazy[node<<1] += val;
			lazy[(node<<1) + 1] += val;
			sTree[(node<<1)] += val;
			sTree[(node<<1) + 1] += val; 
			lazy[node] = 0;
		}
		
		int query(int l, int r)
		{
			return query(1, 1, N, l, r);
		}
		
		int query(int node, int b, int e, int l, int r)
		{
			if(r < b || e < l)
				return INF;
			if(l <= b && e <= r)
				return sTree[node];
			propagate(node, b, e);
			int q1 = query(node<<1, b, (b+e)/2, l, r);
			int q2 = query((node<<1) +1 , (b+e)/2 + 1, e, l, r);
			return Math.min(q1, q2);
		}
	}

	static class Scanner 
	{
		StringTokenizer st;
		BufferedReader br;

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

		public Scanner(FileReader r){	br = new BufferedReader(r);}

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

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

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

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

		public double nextDouble() throws IOException
		{
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if(x.charAt(0) == '-')
			{
				neg = true;
				start++;
			}
			for(int i = start; i < x.length(); i++)
				if(x.charAt(i) == '.')
				{
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				}
				else
				{
					sb.append(x.charAt(i));
					if(dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg?-1:1);
		}

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


	}
}