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.text.DecimalFormat;
import java.util.*;
import java.awt.*;
import java.awt.geom.Point2D;

public class Main implements Runnable {

	static BufferedReader br = new BufferedReader(new InputStreamReader(
			System.in));
	static PrintWriter out = new PrintWriter(new BufferedOutputStream(
			System.out) );
	static StringTokenizer st = new StringTokenizer("");

	public static String next() {
		try {
			while (!st.hasMoreTokens()) {
				String s = br.readLine();
				if (s == null)
					return null;
				st = new StringTokenizer(s);
			}
			return st.nextToken();
		} catch (Exception e) {
			return null;
		}
	}

	public static String nextLine() {
		try {
			st = new StringTokenizer("");
			return	br.readLine();
		} catch (Exception e) {
			return null;
		}
	}

	public static void main(String[] asda) throws Exception {
		new Thread(null, new Main(), "Main", 1 << 26).start();
	}

	public void run() {
	
		String s = next();
		SegmentTree t = new SegmentTree( s );
		
		int M = Integer.parseInt( next() );
		while	(M-- > 0)	{

			int L = Integer.parseInt( next() ) - 1;
			int R = Integer.parseInt( next() ) - 1;

			out.println( t.max(L, R) );
		}
		//
		out.flush();
		System.exit(0);
	}
}


class SegmentTree	{
	Node [] data;
	int N;
	
	SegmentTree(String s)	{
		N = s.length();
		int size = 1;
		while	( (size <<= 1) < N );
		N = size;
		data = new Node[size << 1];
		
		// fill leafs
		for (int i = 0; i < s.length(); i++)	{
			int open = s.charAt(i) == '(' ? 1 : 0;
			int closed = open ^ 1;
			Node node = new Node(open, closed);
			data[i + N] = node;
		}
		
		// fill nodes
		for (int k = N - 1; k > 0; k--)	{
			data[k] = merge( data[k << 1], data[(k << 1) + 1] );
		}
	}
	
	void flip(int id)	{
		id += N;
		
		data[id].flip();
		id >>= 1;
		
		while	(id > 0)	{
			data[id] = merge( data[id << 1], data[(id << 1) + 1] );
			id >>= 1;
		}
	}
	
	int max(int L, int R)	{
		R += N; L += N;
		Node left = null, right = null;
		while	(L <= R)	{
			if	( L == R )	{
				left = merge(left, data[R]);
				break;
			}
			if	( (L&1) != 0 )	left = merge( left, data[L++] );
			if	( (R&1) == 0 )	right = merge( data[R--], right );
			L >>= 1;	R >>= 1;
		}
		
		left = merge(left, right);
		return	left.max;
	}
	
	Node merge(Node x, Node y)	{
		if	( x == null )
			return	y;
		if	( y == null )
			return	x;
		
		int min = Math.min(x.open, y.closed);
		
		Node node = new Node( x.open + y.open - min, x.closed + y.closed - min );
		node.max = x.max + y.max + min + min;
		return	node;
	}
}

class Node	{
	int open;	// number of items opened
	int closed; // number of items not closed
	int max = 0;
	
	Node(int a, int b)	{
		open = a;
		closed = b;
	}
	void flip()	{
		open ^= 1;
		closed ^= 1;
	}
	public String toString()	{
		return	String.format("(%d, %d)", open, closed);
	}
}






