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;
using namespace std;
namespace io {
const int __SIZE = (1 << 21) + 1;
char ibuf[__SIZE], *iS, *iT, obuf[__SIZE], *oS = obuf, *oT = oS + __SIZE - 1,
                                           __c, qu[55];
int __f, qr, _eof;
inline void flush() { fwrite(obuf, 1, oS - obuf, stdout), oS = obuf; }
inline void gc(char &x) {
  x = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin),
                   (iS == iT ? EOF : *iS++))
                : *iS++);
}
inline void pc(char x) {
  *oS++ = x;
  if (oS == oT) flush();
}
inline void pstr(const char *s) {
  int __len = strlen(s);
  for (__f = 0; __f < __len; ++__f) pc(s[__f]);
}
inline void gstr(char *s) {
  for (__c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin),
                         (iS == iT ? EOF : *iS++))
                       : *iS++);
       __c < 32 || __c > 126 || __c == ' ';)
    __c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                    : *iS++);
  for (; __c > 31 && __c < 127 && __c != ' ';
       ++s, __c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin),
                              (iS == iT ? EOF : *iS++))
                            : *iS++))
    *s = __c;
  *s = 0;
}
template <class I>
inline bool gi(I &x) {
  _eof = 0;
  for (__f = 1,
      __c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin),
                        (iS == iT ? EOF : *iS++))
                      : *iS++);
       (__c < '0' || __c > '9') && !_eof;
       __c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin),
                         (iS == iT ? EOF : *iS++))
                       : *iS++)) {
    if (__c == '-') __f = -1;
    _eof |= __c == EOF;
  }
  for (x = 0; __c <= '9' && __c >= '0' && !_eof;
       __c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin),
                         (iS == iT ? EOF : *iS++))
                       : *iS++))
    x = x * 10 + (__c & 15), _eof |= __c == EOF;
  x *= __f;
  return !_eof;
}
template <class I>
inline void print(I x) {
  if (!x) pc('0');
  if (x < 0) pc('-'), x = -x;
  while (x) qu[++qr] = x % 10 + '0', x /= 10;
  while (qr) pc(qu[qr--]);
}
struct Flusher_ {
  ~Flusher_() { flush(); }
} io_flusher_;
}  // namespace io
using io::gc;
using io::gi;
using io::gstr;
using io::pc;
using io::print;
using io::pstr;
void scan() { return; }
template <class T, typename... Args>
void scan(T &a, Args &&...args) {
  gi(a);
  scan(args...);
  return;
}
template <typename T>
void scerr(T a, T b) {
  for (auto it = a; it != b; ++it) cerr << *it << " ";
  cerr << '\n';
}
void cer() {
  cerr << "\n";
  return;
}
template <class T, typename... Args>
void cer(T a, Args... args) {
  cerr << a << " ";
  cer(args...);
  return;
}
const int N = 1e6 + 2;
const int M = 4e6 + 2;
const int mod = 998244353;
const int inf = 2e9 + 3;
const long long INF = 1e16;
void data() {}
char s[N];
int m, l, r, n, pref[N], suff[N];
struct {
  int s[M] = {0};
  void upd(int pos, int val, int v = 1, int tl = 1, int tr = n) {
    if (tl == tr) return void(s[v] = val);
    int tm = (tl + tr) / 2;
    if (pos <= tm)
      upd(pos, val, v * 2, tl, tm);
    else
      upd(pos, val, v * 2 + 1, tm + 1, tr);
    s[v] = min(s[v * 2], s[v * 2 + 1]);
  }
  int get(int l, int r, int v = 1, int tl = 1, int tr = n) {
    if (l <= tl && tr <= r) return s[v];
    if (tr < l || r < tl) return inf;
    int tm = (tl + tr) / 2;
    return min(get(l, r, v * 2, tl, tm), get(l, r, v * 2 + 1, tm + 1, tr));
  }
} t[2];
int main() {
  data();
  gstr(s);
  n = strlen(s);
  for (int i = 1; i <= n; ++i) {
    pref[i] = pref[i - 1] + (s[i - 1] == '(' ? 1 : -1);
    suff[n - i + 1] = suff[n - i + 2] + (s[n - i] == ')' ? 1 : -1);
    t[0].upd(i, pref[i]);
    t[1].upd(n - i + 1, suff[n - i + 1]);
  }
  scan(m);
  while (m--) {
    scan(l, r);
    int ans1 = max(0, -(t[0].get(l, r) - pref[l - 1]));
    int ans2 = max(0, -(t[1].get(l, r) - suff[r + 1]));
    print(r - l + 1 - ans1 - ans2);
    pc('\n');
  }
}
