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.util.*;
import java.io.*;

public class C2 {
	public static long time = 0;

	public static void main(String[] args) throws Exception {
		time = System.currentTimeMillis();
		solve();
		out.flush();
	}

	public static void solve() throws Exception {
		char[] l1 = nx().toCharArray();
		IntL stk = new IntL();
		ArrayList<int[]> pairList = new ArrayList<>();
		for (int i =0 ; i < l1.length; i++){
			if (l1[i] == '('){
				stk.add(i);
			}
			else {
				if (stk.size > 0){
					int left = stk.pop();
					int right = i;
					pairList.add(new int[]{left, right});
				}
			}
		}
		Collections.sort(pairList, new Comparator<int[]>() {
			@Override
			public int compare(int[] l1, int[] l2) {
				if (l1[0] - l2[0] != 0) return l1[0] - l2[0];
				return l1[1] - l2[1];
			}
		});
		
		
		
		int qno = ni();
		final int[] qLeft = new int[qno];
		final int[] qRight = new int[qno];
		for (int i =0 ; i < qno; i++){
			qLeft[i] = ni();
			qRight[i] = ni();
		}
		Integer[] order = new Integer[qno];
		for (int i =0 ; i < qno; i++){
			order[i] = i;
		}
		Arrays.sort(order, new Comparator<Integer>() {
			@Override
			public int compare(Integer n1, Integer n2) {
				int temp1 = qLeft[n1] - qLeft[n2];
				if (temp1 != 0) return temp1;
				return qRight[n1] - qRight[n2];
			}
		});
		
		BIT t1 = new BIT(l1.length + 3);
		for (int [] e: pairList){
			t1.add(e[1], 1);
		}
		
		int[] fin = new int[qno];
		int curLeft = 0;
		
		
//		px(order);
		int removePtr = 0;
		for (int e: order){
			int left1 = qLeft[e];
			int right1 = qRight[e];
			for (;;){
				if (removePtr >= pairList.size()) break;
				int xLeft = pairList.get(removePtr)[0];
				if (xLeft >= left1 - 1) break;
				t1.add(pairList.get(removePtr)[1], -1);
				removePtr++;
			}
//			px(left1, right1);
//			px(t1.sumString());
			int curAns = t1.sum(right1);
//			px(curAns * 2);
			fin[e] = curAns << 1;
		}
		for (int e: fin){
			pn(e);
		}
	}

	public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	public static StringTokenizer st = null;

	public static String nx() throws Exception {
		for (; st == null || !st.hasMoreTokens();) {
			String k1 = in.readLine();
			if (k1 == null) return null;
			st = new StringTokenizer(k1);
		}
		return st.nextToken();
	}

	public static int ni() throws Exception {
		return Integer.parseInt(nx());
	}

	public static long nl() throws Exception {
		return Long.parseLong(nx());
	}

	public static double nd() throws Exception {
		return Double.parseDouble(nx());
	}

	public static void px(Object... l1) {
		System.out.println(Arrays.deepToString(l1));
	}

	public static boolean FLUSH = false;
	public static PrintWriter out = new PrintWriter(System.out, FLUSH);

	public static void p(Object... l1) {
		for (int i = 0; i < l1.length; i++) {
			if (i != 0) out.print(' ');
			out.print(l1[i].toString());
		}
	}

	public static void pn(Object... l1) {
		for (int i = 0; i < l1.length; i++) {
			if (i != 0) out.print(' ');
			out.print(l1[i].toString());
		}
		out.println();
	}

	public static void pn(Collection l1) {
		boolean first = true;
		for (Object e : l1) {
			if (first) first = false;
			else out.print(' ');
			out.print(e.toString());
		}
		out.println();
	}

	private static class BIT {
		int[] vs;

		public BIT(int n) {
			vs = new int[n + 1];
		}

		public void add(int idx, int n1) {
			for (int i = idx + 1; i < vs.length; i += i & -i) {
				vs[i] += n1;
			}
		}

		public int sum(int t) {
			return sum(0, t);
		}

		public int sum(int s, int t) {
			if (s > 0) return sum(0, t) - sum(0, s);
			int res = 0;
			for (int i = t; i > 0; i -= i & -i) {
				res += vs[i];
			}
			return res;
		}

		@Override
		public String toString() {
			List<Integer> fin = new ArrayList();
			for (int i = 0; i < vs.length - 1; i++) {
				fin.add(sum(0, i + 1) - sum(0, i));
			}
			return fin.toString();
		}
	}

	private static class IntL implements Iterable<Integer> {
		public int[] cont = null;
		public int size = 0;

		public IntL(int initialCapacity) {
			this.cont = new int[initialCapacity];
		}

		public IntL() {
			this(5);
		}

		public void add(int e) {
			if (size == cont.length) {
				cont = Arrays.copyOf(cont, ((cont.length * 3) >> 1) + 1);
			}
			cont[size++] = e;
		}

		public int pop() {
			size--;
			return cont[size];
		}

		@Override
		public String toString() {
			StringBuilder fin = new StringBuilder();
			fin.append('{');
			for (int i = 0; i < size; i++) {
				if (i != 0) fin.append(", ");
				fin.append(cont[i]);
			}
			fin.append('}');
			return fin.toString();
		}

		@Override
		public Iterator<Integer> iterator() {
			return new It();
		}

		public class It implements Iterator<Integer> {
			int ptr = 0;

			@Override
			public boolean hasNext() {
				if (ptr < size) return true;
				return false;
			}

			@Override
			public Integer next() {
				int fin = cont[ptr];
				ptr++;
				return fin;
			}

			@Override
			public void remove() {}
		}
	}

}
