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.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.Locale;
import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.CopyOnWriteArrayList;

public class Little {

	public static void main(String[] args) {
		Locale.setDefault(Locale.US);
		InputStream inputstream = System.in;
		OutputStream outputstream = System.out;
		FastReader in = new FastReader(inputstream);
		PrintWriter out = new PrintWriter(outputstream);
		TaskA solver = new TaskA();
		// int testcase = in.ni();
		for (int i = 0; i < 1; i++)
			solver.solve(i, in, out);
		out.close();

	}

}

class State {

	int len;
	int left;
	int right;

	public State(int len, int left, int right) {
		this.len = len;
		this.left = left;
		this.right = right;
	}
}

class SegmentTree {
	int n;
	int lo[];
	int hi[];
	int max[];
	int l[];
	int r[];

	public SegmentTree(int m, String s) {
		n = 4 * m + 1;
		lo = new int[n];
		hi = new int[n];
		max = new int[n];
		l = new int[n];
		r = new int[n];
		build(1, 0, m - 1, s);
	}

	void build(int i, int low, int high, String s) {
		hi[i] = high;
		lo[i] = low;

		if (hi[i] == lo[i]) {
			if (s.charAt(low) == '(') {
				l[i]++;
			} else {
				r[i]++;
			}

			return;
		}

		int mid = low + (high - low) / 2;
		build(2 * i, low, mid, s);
		build(2 * i + 1, mid + 1, high, s);
		int match = Math.min(l[2 * i], r[2 * i + 1]);
		max[i] = match * 2 + max[2 * i] + max[2 * i + 1];
		r[i] = r[2 * i] + r[2 * i + 1] - match;
		l[i] = l[2 * i] + l[2 * i + 1] - match;

	}

	State query(int i, int left, int right) {

		if (hi[i] < left || lo[i] > right) {
			return new State(0, 0, 0);
		}

		if (lo[i] == hi[i]) {
			return new State(0, l[i], r[i]);
		}

		if (lo[i] >= left && hi[i] <= right) {
			return new State(max[i], l[i], r[i]);
		}

		State leftans = query(2 * i, left, right);
		State rightans = query(2 * i + 1, left, right);

		int match = Math.min(leftans.left, rightans.right);
		int length = match * 2 + leftans.len + rightans.len;
		int rights = leftans.right + rightans.right - match;
		int lefts = leftans.left + rightans.left - match;

		State res = new State(length, lefts, rights);
		return res;

	}

}

class TaskA {

	public void solve(int testnumber, FastReader in, PrintWriter out) {
		String s = in.ns();
		int m = in.ni();
		SegmentTree tree = new SegmentTree(s.length(), s);
		while (m > 0) {
			int l = in.ni()-1;
			int r = in.ni()-1;
			out.println(tree.query(1, l, r).len);
			m--;
		}
	}
}

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

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

	public FastReader() {

	}

	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 ni() {
		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 ns() {
		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 isWhitespace(c);
	}

	public static boolean isWhitespace(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	public int[] iArr(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = ni();
		}
		return a;
	}

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

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

}