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.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.InputMismatchException;
import java.util.SortedSet;
import java.util.TreeSet;

public class Main {
	static final long mod=(long)(1e9+7);
	static int d[],a[],func[],seg[],open[],close[],lazy[];
	static long ansquery=0;
	static node node;
	static SortedSet<String> hs;
	public static void main(String[] args) throws Exception{
		int m;
		//long start=System.nanoTime();
		//BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		InputReader in =new InputReader(System.in);
		OutputWriter out=new OutputWriter(System.out);
		char a[]=in.readString().toCharArray();
		seg=new int[4*a.length];
		open=new int[4*a.length];
		close=new int[4*a.length];
		build(a,0,a.length-1,1);
		m=in.readInt();
		while(m-->0){
			int x=in.readInt();
			int y=in.readInt();
			x--;y--;
			node=query(a,0,a.length-1,x,y,1);
			out.printLine(node.s);
		}
		out.flush();
		out.close();
	}
	

	private static node query(char[] a, int start, int end, int x, int y, int index) {
		if(y<start || x>end){
			return node=new node(0,0,0);
		}
		if(x<=start && y>=end){
			return node=new node(seg[index],open[index],close[index]);
		}
		int mid=getmid(start,end);
		node node1=query(a,start,mid,x,y,2*index);
		node node2=query(a,mid+1,end,x,y,2*index+1);
		int tmp=Math.min(node1.o, node2.c);
		int t=node1.s+node2.s+2*tmp;
		int o=node1.o+node2.o-tmp;
		int c=node1.c+node2.c-tmp;
		return node=new node(t,o,c);
	}

	private static void build(char[] a, int start, int end, int index) {
		if(start==end){
			if(a[start]=='('){
				open[index]+=1;
			}
			else
				close[index]+=1;
			return;
		}
		int mid=getmid(start,end);
		build(a,start,mid,2*index);
		build(a,mid+1,end,2*index+1);
		int tmp=Math.min(open[2*index], close[2*index+1]);
		seg[index]=seg[2*index]+seg[2*index+1]+2*tmp;
		open[index]=open[2*index]+open[2*index+1]-tmp;
		close[index]=close[2*index]+close[2*index+1]-tmp;
	}


	private static int getmid(int start, int end) {
		// TODO Auto-generated method stub
		return start+(end-start)/2;
	}
}

class node{
	public node(int i, int j, int k) {
		s=i;
		o=j;
		c=k;
	}

	int s, o,c ;
	
}

class InputReader {

	private InputStream stream;
	private byte[] buf = new byte[1024];
	private int curChar;
	private int numChars;
	private SpaceCharFilter filter;

	public InputReader(InputStream stream) {
		this.stream = stream;
	}

	public int read() {
		if (numChars == -1)
			throw new InputMismatchException();
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int readInt() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public String readString() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		if (filter != null)
			return filter.isSpaceChar(c);
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	public String next() {
		return readString();
	}

	public interface SpaceCharFilter {
		public boolean isSpaceChar(int ch);
	}
}

class OutputWriter {
	private final PrintWriter writer;

	public OutputWriter(OutputStream outputStream) {
		writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
	}

	public OutputWriter(Writer writer) {
		this.writer = new PrintWriter(writer);
	}

	public void print(Object...objects) {
		for (int i = 0; i < objects.length; i++) {
			if (i != 0)
				writer.print(' ');
			writer.print(objects[i]);
		}
	}

	public void printLine(Object...objects) {
		print(objects);
		writer.println();
	}

	public void close() {
		writer.close();
	}

	public void flush() {
		writer.flush();
	}

}