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;
template <typename T>
T next_int() {
  T x = 0, p = 1;
  char ch;
  do {
    ch = getchar();
  } while (ch <= ' ');
  if (ch == '-') {
    p = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  return p * x;
}
string next_token() {
  char ch;
  string ans = "";
  do {
    ch = getchar();
  } while (ch <= ' ');
  while (ch > ' ') {
    ans += ch;
    ch = getchar();
  }
  return ans;
}
const long long INF = (long long)1e18;
const int INFINT = (int)1e9 + 227 + 1;
const int MAXN = (int)1e6 + 227 + 1;
const int MOD = (int)1e9 + 7;
const long double EPS = 1e-9;
long long bin_pow(long long a, long long b) {
  if (!b) return 1;
  long long ans = bin_pow(a, b / 2);
  ans = ans * ans % MOD;
  if (b % 2) ans = ans * a % MOD;
  return ans;
}
struct fenwik {
  vector<long long> f;
  fenwik(int len) { f.resize(len + 227 + 1, 0); }
  void inc_s(int p, long long c) {
    for (int i = p; i < f.size(); i += (i & (-i))) f[i] += c;
  }
  void inc(int p, long long c) {
    inc_s(1, c);
    inc_s(p + 1, -c);
  }
  long long get(int p) {
    long long ans = 0;
    for (int i = p; i > 0; i -= (i & (-i))) ans += f[i];
    return ans;
  }
};
int main() {
  string a = next_token();
  int n = a.size();
  fenwik f(n), s(n);
  int m;
  cin >> m;
  vector<vector<pair<int, int> > > b(n);
  vector<int> ans(m);
  for (int i = 0; i < m; i++) {
    int l = next_int<int>() - 1;
    int r = next_int<int>() - 1;
    b[r].push_back(make_pair(l, i));
  }
  for (int i = 0; i < a.size(); i++) {
    if (a[i] == '(') {
      f.inc(i + 1, 1);
    } else {
      int l = 1;
      int r = i + 1;
      while (r - l > 1) {
        int c = (l + r) / 2;
        if (f.get(c) > 0)
          l = c;
        else
          r = c;
      }
      int pe = -1;
      if (f.get(r) > 0)
        pe = r;
      else if (f.get(l) > 0)
        pe = l;
      if (pe != -1) {
        s.inc(pe, 1);
        f.inc(pe, -1);
      }
    }
    for (int j = 0; j < b[i].size(); j++) {
      ans[b[i][j].second] = s.get(b[i][j].first + 1) * 2;
    }
  }
  for (int i = 0; i < m; i++) cout << ans[i] << "\n";
}
