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>
struct data {
  int a, b, c;
};
data idx[2097160];
char ch[1000010];
int len;
void go(int l, int r) {
  int i, L, R, min;
  for (i = l; i <= r; i += 2) {
    if (i == r) {
      idx[i / 2] = idx[i];
    } else {
      L = i, R = i + 1;
      min = (idx[L].b < idx[R].c) ? idx[L].b : idx[R].c;
      idx[i / 2].a = idx[L].a + idx[R].a + min;
      idx[i / 2].b = idx[L].b + idx[R].b - min;
      idx[i / 2].c = idx[L].c + idx[R].c - min;
    }
  }
  if (l != r) go(l / 2, r / 2);
}
int Min(int a, int b) { return (a > b) ? b : a; }
data find(int l, int r, int L, int R, int now) {
  int m;
  data ret = {}, g;
  if (l <= L && R <= r) return idx[now];
  m = (L + R) / 2;
  if (l <= m) ret = find(l, r, L, m, now * 2);
  if (m < r) {
    g = find(l, r, m + 1, R, now * 2 + 1);
    int t = Min(ret.b, g.c);
    ret.a += g.a + t;
    ret.b += g.b - t;
    ret.c += g.c - t;
  }
  return ret;
}
int main(void) {
  int i, lev, term, q, a, b;
  scanf("%s", &ch[1]);
  len = strlen(&ch[1]);
  for (lev = 1;; lev++) {
    if ((1 << lev) >= len) break;
  }
  term = (1 << lev) - 1;
  for (i = 1; i <= len; i++) {
    if (ch[i] == '(')
      idx[term + i].b++;
    else
      idx[term + i].c++;
  }
  go(term + 1, term + len);
  scanf("%d", &q);
  for (; q >= 1; q--) {
    scanf("%d %d", &a, &b);
    printf("%d\n", find(term + a, term + b, term + 1, term * 2 + 1, 1).a * 2);
  }
  return false;
}
