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 int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fll;
struct S {
  int a;
  int b;
  int c;
  S(int a = 0, int b = 0, int c = 0) : a(a), b(b), c(c) {}
};
template <typename T>
struct F1 {
  int L, R;
  T add;
  F1(T add) : add(add) {}
  void apply_aggregate(T& old) const {}
  void compose(const F1<T>& op) {}
  void operator=(const F1& op) {}
};
template <typename T, typename F>
class SegmentTree {
 private:
  const int n, h;
  vector<T> st;
  vector<F> d;
  const T T_id;
  const F F_id;
  T combine(const T& resl, const T& resr) {
    int t = min(resl.b, resr.c);
    return {resl.a + resr.a + 2 * t, resl.b + resr.b - t, resl.c + resr.c - t};
  }
  void apply(int p) {
    d[p].apply_aggregate(st[p]);
    if (p < n) {
      d[p << 1].compose(d[p]);
      d[p << 1 | 1].compose(d[p]);
    }
    d[p] = F_id;
  }
  void build(int p) {
    while (p > 1) {
      p >>= 1;
      apply(p << 1);
      apply(p << 1 | 1);
      st[p] = combine(st[p << 1], st[p << 1 | 1]);
    }
  }
  void push(int p) {
    for (int second = h; second >= 0; --second) {
      int i = p >> second;
      apply(i);
      if (i < n) {
        apply(i << 1);
        apply(i << 1 | 1);
      }
    }
  }

 public:
  SegmentTree(const vector<T>& a, T T_id, F F_id)
      : n(a.size()),
        h(sizeof(int) * 8 - __builtin_clz(n)),
        T_id(T_id),
        F_id(F_id) {
    st.assign(2 * n, T_id);
    d.assign(2 * n, F_id);
    for (int i = 0; i < n; ++i) {
      st[n + i] = a[i];
      d[n + i].L = d[n + i].R = i;
    }
    for (int i = n - 1; i > 0; --i) {
      st[i] = combine(st[i << 1], st[i << 1 | 1]);
      d[i].L = d[i << 1].L;
      d[i].R = d[i << 1 | 1].R;
    }
  }
  void update(int l, int r, F op) {
    l += n, r += n;
    int l0 = l, r0 = r;
    for (; l < r; l >>= 1, r >>= 1) {
      if (l & 1) {
        d[l].compose(op);
        apply(l++);
      }
      if (r & 1) {
        d[r - 1].compose(op);
        apply(--r);
      }
    }
    build(l0);
    build(r0 - 1);
  }
  T query(int l, int r) {
    l += n, r += n;
    push(l);
    push(r - 1);
    T resl = T_id, resr = T_id;
    for (; l < r; l >>= 1, r >>= 1) {
      if (l & 1) resl = combine(resl, st[l++]);
      if (r & 1) resr = combine(st[--r], resr);
    }
    return combine(resl, resr);
  }
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  string second;
  cin >> second;
  int n = second.size();
  int m;
  cin >> m;
  vector<S> A(n);
  for (int i = 0; i < n; ++i) A[i] = S(0, second[i] == '(', second[i] == ')');
  SegmentTree<S, F1<S>> T(A, S(), F1<S>(S(0)));
  for (int j = 0; j < m; ++j) {
    int l, r;
    cin >> l >> r;
    l--;
    r--;
    cout << T.query(l, r + 1).a << '\n';
  }
  exit(0);
}
