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.BufferedReader;
import java.io.FileNotFoundException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;
import java.lang.Long;

public class Test {
	static long mod = 1000000007;
	static TreeSet[] dp;

	static int contains;

	public static void main(String[] args) throws FileNotFoundException {
		PrintWriter out = new PrintWriter(System.out);
		Scanner in = new Scanner();
		String line = in.next();
		int n = in.nextInt();
		int m = line.length();

		int[] pre = new int[m];
		int[] all = new int[m];
		for (int i = 0; i < m; i++) {
			if (line.charAt(i) == '(') {
				all[i]++;
			} else {
				pre[i]++;
				all[i]--;
			}
			if (i > 0) {
				pre[i] += pre[i - 1];
				all[i] += all[i - 1];
			}
		}
		Node root = new Node(0, m - 1);
		update(root, 0, m - 1, all);
		for (int i = 0; i < n; i++) {
			int a = in.nextInt() - 1;
			int b = in.nextInt() - 1;
			int re = pre[b] - (a > 0 ? pre[a - 1] : 0);
			re -= Math.max(0 , (a > 0 ? all[a - 1] : 0) - query(root, a > 0 ? a - 1 : 0, b));
			//System.out.println(a + " " + b + " " + re);
			out.println((2 * re));
		}
		out.close();
	}

	static int query(Node node, int l, int r) {
		if (node.l > r || node.r < l) {
			return Integer.MAX_VALUE;
		}
		if (l <= node.l && r >= node.r) {
			return node.min;
		} else {
			int v = query(node.left, l, r);
			int v1 = query(node.right, l, r);
			return Math.min(v, v1);
		}
	}

	static int update(Node node, int l, int r, int[] all) {
		if (l == r) {
			node.min = all[l];
		} else {
			int mid = (l + r) / 2;
			node.left = new Node(l, mid);
			int v = update(node.left, l, mid, all);
			node.right = new Node(mid + 1, r);
			int v1 = update(node.right, mid + 1, r, all);
			node.min = Math.min(v, v1);
		}
		return node.min;
	}

	static class Node {
		int l, r, min;
		Node left, right;

		public Node(int l, int r) {
			super();
			this.l = l;
			this.r = r;
		}

	}

	static int crossProduct(Point a, Point b) {
		return a.x * b.y + a.y * b.x;
	}

	static long squareDist(Point a) {
		long x = a.x;
		long y = a.y;
		return x * x + y * y;
	}

	static Point minus(Point a, Point b) {
		return new Point(a.x - b.x, a.y - b.y);
	}

	public static boolean nextPer(int[] data) {
		int i = data.length - 1;
		while (i > 0 && data[i] < data[i - 1]) {
			i--;
		}
		if (i == 0) {
			return false;
		}
		int j = data.length - 1;
		while (data[j] < data[i - 1]) {
			j--;
		}
		int temp = data[i - 1];
		data[i - 1] = data[j];
		data[j] = temp;
		Arrays.sort(data, i, data.length);
		return true;
	}

	static class Point {
		int x, y;

		public Point(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}

		public String toString() {
			return "{" + x + " " + y + "}";
		}

	}

	static class Entry implements Comparable<Entry> {
		int x, cost;

		public Entry(int x, int cost) {
			super();
			this.x = x;
			this.cost = cost;
		}

		public int compareTo(Entry o) {
			// TODO Auto-generated method stub
			if (cost > o.cost) {
				return 1;
			} else if (cost == o.cost) {
				return -1;
			}

			return 0;
		}
	}

	static int gcd(int a, int b) {
		if (b == 0) {
			return a;
		}
		return gcd(b, a % b);
	}

	static class Scanner {

		BufferedReader br;
		StringTokenizer st;

		public Scanner() throws FileNotFoundException {
			// System.setOut(new PrintStream(new
			// BufferedOutputStream(System.out), true));
			br = new BufferedReader(new InputStreamReader(System.in));
			// br = new BufferedReader(new InputStreamReader(new
			// FileInputStream(new File("B-large.in"))));
		}

		public String next() {

			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (Exception e) {
					throw new RuntimeException();
				}
			}
			return st.nextToken();
		}

		public long nextLong() {
			return Long.parseLong(next());
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

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

		public boolean endLine() {
			try {
				String next = br.readLine();
				while (next != null && next.trim().isEmpty()) {
					next = br.readLine();
				}
				if (next == null) {
					return true;
				}
				st = new StringTokenizer(next);
				return st.hasMoreTokens();
			} catch (Exception e) {
				throw new RuntimeException();
			}
		}
	}
}