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;
stack<int> s;
string p;
int a, b, c, q, bit[1010000], poz, rj[1010000];
vector<pair<int, pair<int, int> > > v;
void update(long long x, long long v) {
  for (; x < 1010000; x += x & -x) bit[x] += v;
}
long long read(long long x) {
  long long ret = 0;
  while (x > 0) {
    ret += bit[x];
    x -= x & -x;
  }
  return ret;
}
int main(void) {
  cin >> p >> q;
  for (int i = 0; i < q; ++i) {
    cin >> a >> b;
    v.push_back(pair<int, pair<int, int> >(b - 1, make_pair(a - 1, i)));
  }
  sort(v.begin(), v.end());
  for (int i = 0; i < p.size(); ++i) {
    if (p[i] == '(') {
      s.push(i);
    } else {
      if (!s.empty()) {
        a = s.top();
        s.pop();
        update(1, 2);
        update(a + 2, -2);
      }
    }
    if (poz < q) {
      while (v[poz].first == i && poz < q) {
        rj[v[poz].second.second] = read(v[poz].second.first + 1);
        poz++;
      }
    }
  }
  for (int i = 0; i < q; ++i) cout << rj[i] << endl;
  return 0;
}
