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

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Agostinho Junior
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		OutputWriter out = new OutputWriter(outputStream);
		TaskE solver = new TaskE();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskE {
	OutputWriter out;
	InputReader in;
	public void solve(int testNumber, InputReader in, OutputWriter out) {
		this.in = in; this.out = out;
		char[] s = in.readLine().toCharArray();
		Node root = new Node(s, 0, s.length - 1);
		int m = in.readInt();
		while (m-- > 0) {
			int l = in.readInt() - 1;
			int r = in.readInt() - 1;
			out.println(root.getMaxInRange(l, r));
		}
	}
}

class Node {
	private int start;
	private int end;
	private int opened;
	private int closed;
	private int maxLen;
	private Node[] children;
	public Node(char[] s, int start, int end) {
		this.start = start;
		this.end = end;
		if (start == end) {
			if (s[start] == '(') {
				opened = 1;
			} else {
				closed = 1;
			}
		} else {
			children = new Node[2];
			int mid = (start + end) / 2;
			int[][] positions = {{start, mid}, {mid + 1, end}};
			for (int i = 0; i < 2; i++) {
				int newStart = positions[i][0];
				int newEnd = positions[i][1];
				children[i] = new Node(s, newStart, newEnd);
			}
			calcLen();
		}
		//System.out.printf("%s, %d, %d:: op: %d, cl: %d, maxLen: %d\n", new String(Arrays.copyOfRange(s, start, end + 1)), start, end, opened, closed, maxLen);
	}
	private Node(Node[] children, int start, int end) {
		this.children = children;
		this.start = start;
		this.end = end;
		calcLen();
	}
	private void calcLen() {
		int min = Math.min(children[0].opened, children[1].closed);
		opened = children[0].opened - min + children[1].opened;
		closed = children[0].closed + children[1].closed - min;
		maxLen = (end - start + 1) - (opened + closed);
	}
	public Node getMaxInRange(int queryStart, int queryEnd) {
		if (end < queryStart || queryEnd < start) {
			return null;
		}
		if (queryStart <= start && end <= queryEnd) {
			return this;
		}
		Node[] temp = new Node[2];
		for (int i = 0; i < 2; i++) {
			temp[i] = children[i].getMaxInRange(queryStart, queryEnd);
		}
		for (int i = 0; i < 2; i++) {
			if (temp[i] == null) {
				return temp[i ^ 1];
			}
		}
		//System.out.printf("best: %s\n", new Node(temp, Math.max(queryStart, start), Math.min(queryEnd, end)));
		return new Node(temp, Math.max(queryStart, start), Math.min(queryEnd, end));
	}
	public String toString() {
		return maxLen + "";
	}
}

class OutputWriter {
	private PrintWriter output;
	public OutputWriter() {
		this(System.out);
	}
	public OutputWriter(OutputStream out) {
		output = new PrintWriter(out);
	}
	public OutputWriter(Writer writer) {
		output = new PrintWriter(writer);
	}
	public void println(Object o) {
		output.println(o);
	}
	public void close() {
		output.close();
	}
}

class InputReader {
	private BufferedReader input;
	private StringTokenizer line = new StringTokenizer("");
	public InputReader() {
		this(System.in);
	}
	public InputReader(InputStream in) {
		input = new BufferedReader(new InputStreamReader(in));
	}
	public InputReader(String s) {
		try {
			input = new BufferedReader(new FileReader(s));
		} catch(IOException io) { io.printStackTrace(); System.exit(0);}
	}
	public void fill() {
		try {
			if(!line.hasMoreTokens()) line = new StringTokenizer(input.readLine());
		} catch(IOException io) { io.printStackTrace(); System.exit(0);}
	}
	public int readInt() {
		fill();
		return Integer.parseInt(line.nextToken());
	}
	public String readLine() {
		String s = "";
		try {
			s = input.readLine();
		} catch(IOException io) {io.printStackTrace(); System.exit(0);}
		return s;
	}
}

