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>
const int FENLEN = 1 << 17;
const int MAX_LEN = 1000005;
using namespace std;
class fenwick {
  int *val;

 public:
  fenwick() {
    val = new int[FENLEN];
    for (int i = 0; i < FENLEN; i++) {
      val[i] = 0;
    }
  }
  void add(int index, int num) {
    for (int i = index; i < FENLEN; i += i & -i) {
      val[i] += num;
    }
  }
  int get(int index) {
    int ans = 0;
    for (int i = index; i > 0; i -= i & -i) {
      ans += val[i];
    }
    return ans;
  }
  int lastzero() {
    int ans = 0;
    for (int i = FENLEN / 2; i != 0; i /= 2) {
      if (get(ans + i) == 0) {
        ans += i;
      }
    }
    return ans;
  }
};
int compr[MAX_LEN];
struct query {
  int left, right, id, ans;
} queries[FENLEN];
bool byright(query p, query q) {
  if (p.right == q.right) {
    return p.id < q.id;
  } else {
    return p.right < q.right;
  }
}
bool orig(query p, query q) { return p.id < q.id; }
int main() {
  ios::sync_with_stdio(false);
  string arr;
  cin >> arr;
  set<int, greater<int> > cpset;
  int queryc;
  cin >> queryc;
  cpset.insert(0);
  for (int i = 0; i < queryc; i++) {
    cin >> queries[i].left >> queries[i].right;
    queries[i].left--;
    queries[i].right--;
    queries[i].id = i;
    cpset.insert(queries[i].left);
  }
  int cur_comp = 1;
  for (auto i = cpset.begin(); i != cpset.end(); i++) {
    compr[*i] = cur_comp;
    cur_comp++;
  }
  sort(queries, queries + queryc, byright);
  int cur_query = 0, cur_left = compr[0];
  fenwick lvl, len;
  for (int i = 0; i < (int)arr.size(); i++) {
    if (compr[i] != 0) {
      cur_left = compr[i];
    }
    if (arr[i] == '(') {
      lvl.add(cur_left, 1);
    } else {
      int lz = lvl.lastzero();
      lvl.add(lz + 1, -1);
      len.add(lz + 1, 2);
    }
    while (i == queries[cur_query].right) {
      queries[cur_query].ans = len.get(compr[queries[cur_query].left]);
      cur_query++;
    }
  }
  sort(queries, queries + queryc, orig);
  for (int i = 0; i < queryc; i++) {
    cout << queries[i].ans << '\n';
  }
}
