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;
const long long MAX = 1000000000000000000;
long long mod = 1000000000;
long double pi = 3.141592653589793238;
void pls() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
long long mul_mod(long long a, long long b, long long m) {
  long long x = 0, y = a;
  while (b > 0) {
    if (b & 1) {
      x = (x + y) % m;
    }
    y = (y + y) % m;
    b >>= 1;
  }
  return x;
}
inline long long modu(long long val, long long modul) {
  return (val % modul + modul) % modul;
}
inline int madd(int x, int y) { return (x % mod + y % mod) % mod; }
inline int msub(int x, int y) { return (mod + x % mod - y % mod) % mod; }
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long powmod(long long a, long long mod, long long p) {
  if (p == 0) return 1;
  long long res;
  long long x = powmod(a, mod, p / 2);
  res = x;
  if (p & 1) x = mul_mod(x, a, mod);
  return mul_mod(x, res, mod);
}
long long exp(long long a, long long p) {
  if (p == 0) return 1;
  long long res;
  long long x = exp(a, p / 2);
  res = x;
  if (p & 1) x = (x * a);
  return (x * res);
}
long long sqt(long long x) {
  long long l = 1LL;
  long long r = x;
  long long res;
  while (l <= r) {
    long long mid = l + (r - l) / 2;
    if (mid * mid <= x) {
      res = mid;
      l = mid + 1;
    } else
      r = mid - 1;
  }
  return res;
}
bool isprime(long long n) {
  for (int i = 2; i <= sqt(n); i++)
    if (n % i == 0) return 0;
  return 1;
}
vector<int> soe(long long upto) {
  vector<bool> prime(upto + 1, 0);
  prime[1] = 1;
  prime[0] = 1;
  for (int i = 2; i <= sqt(upto); i++) {
    if (!prime[i]) {
      for (int j = 2 * i; j <= upto; j += i) prime[j] = 1;
    }
  }
  vector<int> res;
  res.push_back(2);
  for (int i = 3; i < prime.size(); i += 2) {
    if (!prime[i]) res.push_back(i);
  }
  return res;
}
int di[8] = {-1, -1, -1, 1, 1, 1, 0, 0};
int dj[8] = {-1, 0, 1, -1, 0, 1, -1, 1};
int ii[4] = {0, 0, -1, 1};
int jj[4] = {-1, 1, 0, 0};
struct node {
  int o, c, p;
};
int n;
string s;
class sg {
 public:
  vector<node> seg;
  sg(int n) {
    int p = ceil(log2(n));
    seg.resize(pow(2, p + 1) - 1, {0, 0, 0});
  }
  node query(int qs, int qe, int si = 0, int ss = 0, int se = n - 1) {
    if (ss > qe || se < qs || ss > se) return {0, 0, 0};
    if (ss >= qs && se <= qe) return seg[si];
    int mid = (se + ss) / 2;
    node l = query(qs, qe, 2 * si + 1, ss, mid);
    node r = query(qs, qe, 2 * si + 2, mid + 1, se);
    int mn = min(l.o, r.c);
    return {l.o + r.o - mn, l.c + r.c - mn, l.p + r.p + mn};
  }
  void build(int si = 0, int ss = 0, int se = n - 1) {
    if (ss > se) return;
    if (ss == se) {
      if (s[ss] == '(') {
        seg[si] = {1, 0, 0};
      } else {
        seg[si] = {0, 1, 0};
      }
      return;
    }
    int mid = (ss + se) / 2;
    build(2 * si + 1, ss, mid);
    build(2 * si + 2, mid + 1, se);
    int lo = seg[2 * si + 1].o;
    int rc = seg[2 * si + 2].c;
    int mn = min(lo, rc);
    seg[si] = {seg[2 * si + 1].o + seg[2 * si + 2].o - mn,
               seg[2 * si + 1].c + seg[2 * si + 2].c - mn,
               seg[2 * si + 1].p + seg[2 * si + 2].p + mn};
  }
};
void solve() {
  cin >> s;
  n = s.size();
  sg res(n);
  res.build();
  int q;
  cin >> q;
  while (q--) {
    int l, r;
    cin >> l >> r;
    l--;
    r--;
    cout << 2 * res.query(l, r).p << endl;
  }
}
int main() {
  pls();
  solve();
  return 0;
}
