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;
struct LT {
  int a, b, c;
};
char s1[1000007];
struct LTree {
  int l, r;
  int a, b, c;
} tree[4 * 1000007];
void up(int step) {
  int lson = step << 1;
  int rson = (step << 1) | 1;
  int t = min(tree[lson].b, tree[rson].c);
  tree[step].a = tree[lson].a + tree[rson].a + t;
  tree[step].b = tree[lson].b + tree[rson].b - t;
  tree[step].c = tree[lson].c + tree[rson].c - t;
}
void build(int step, int l, int r) {
  tree[step].l = l;
  tree[step].r = r;
  if (l == r) {
    tree[step].a = 0;
    if (s1[l - 1] == '(')
      tree[step].b = 1, tree[step].c = 0;
    else
      tree[step].c = 1, tree[step].b = 0;
    return;
  }
  int mid = (l + r) >> 1;
  int lson = step << 1;
  int rson = (step << 1) | 1;
  build(lson, l, mid);
  build(rson, mid + 1, r);
  up(step);
}
LT cal(int step, int l, int r) {
  if (tree[step].l == l && tree[step].r == r) {
    LT tmp;
    tmp.a = tree[step].a;
    tmp.b = tree[step].b;
    tmp.c = tree[step].c;
    return tmp;
  }
  int mid = (tree[step].l + tree[step].r) >> 1;
  int lson = step << 1;
  int rson = (step << 1) | 1;
  if (r <= mid)
    return cal(lson, l, r);
  else if (l > mid)
    return cal(rson, l, r);
  else {
    LT x1 = cal(lson, l, mid), x2 = cal(rson, mid + 1, r);
    int t = min(x1.b, x2.c);
    LT tmp;
    tmp.a = x1.a + x2.a + t;
    tmp.b = x1.b + x2.b - t;
    tmp.c = x1.c + x2.c - t;
    return tmp;
  }
}
int main() {
  int n, m;
  scanf("%s", s1);
  n = strlen(s1);
  build(1, 1, n);
  scanf("%d", &m);
  for (int i = 0; i < m; i++) {
    int lx, rx;
    scanf("%d%d", &lx, &rx);
    printf("%d\n", cal(1, lx, rx).a * 2);
  }
}
