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 «()(())(())».
#include <bits/stdc++.h>
using namespace std;
const int MAXINT = 1 << 31 - 1;
const long long MAXLONG = (long long)1 << 63 - 1;
const int MAXN = 4 * 1e6;
class Node {
 public:
  int le, ri, go;
  Node(int l, int r, int g) {
    le = l;
    ri = r;
    go = g;
  }
};
int l[MAXN], r[MAXN], g[MAXN];
char arr[MAXN];
int len, q, nn;
void build(int idx, int s, int t) {
  if (s > t) return;
  if (s == t) {
    if (s > len) {
      return;
    }
    if (arr[s - 1] == '(') {
      l[idx]++;
    } else {
      r[idx]++;
    }
    return;
  }
  int md = (s + t) >> 1;
  build(idx * 2, s, md);
  build(idx * 2 + 1, md + 1, t);
  int i1 = idx * 2, i2 = idx * 2 + 1;
  int good = min(l[i1], r[i2]);
  g[idx] = g[i1] + g[i2] + 2 * good;
  l[idx] = l[i1] + l[i2] - good;
  r[idx] = r[i1] + r[i2] - good;
}
Node query(int idx, int s, int t, int from, int to) {
  if (from <= s && t <= to) {
    Node n(l[idx], r[idx], g[idx]);
    return n;
  }
  if (from > t || to < s) {
    return Node(0, 0, 0);
  }
  int md = (s + t) >> 1;
  Node n1 = query(idx * 2, s, md, from, to);
  Node n2 = query(idx * 2 + 1, md + 1, t, from, to);
  Node n(0, 0, 0);
  int good = min(n1.le, n2.ri);
  n.go = n1.go + n2.go + 2 * good;
  n.le = n1.le + n2.le - good;
  n.ri = n1.ri + n2.ri - good;
  return n;
}
int main() {
  while (scanf("%s", arr) != -1) {
    len = strlen(arr);
    nn = 1;
    while (nn < len) {
      nn *= 2;
    }
    memset(l, 0, sizeof(l)), memset(r, 0, sizeof(r)), memset(g, 0, sizeof(g));
    build(1, 1, nn);
    cin >> q;
    for (int i = (0); i < (q); i += 1) {
      int a, b;
      scanf("%d %d", &a, &b);
      Node res = query(1, 1, nn, a, b);
      cout << res.go << endl;
    }
  }
  return 0;
}
