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, typename U>
void upmin(T& a, const U& b) {
  a = min<T>(a, b);
}
template <typename T, typename U>
void upmax(T& a, const U& b) {
  a = max<T>(a, b);
}
template <typename T>
void uniq(T& a) {
  sort(a.begin(), a.end());
  a.erase(unique(a.begin(), a.end()), a.end());
}
template <class T>
string to_s(const T& a) {
  ostringstream os;
  os << a;
  return os.str();
}
template <class T>
T to_T(const string& s) {
  istringstream is(s);
  T res;
  is >> res;
  return res;
}
void fast_io() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}
bool in_rect(int x, int y, int w, int h) {
  return 0 <= x && x < w && 0 <= y && y < h;
}
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
template <typename T>
class FenwickTree {
 public:
  vector<T> a;
  int n;
  FenwickTree(int n) : n(n), a(n + 1) {}
  FenwickTree() {}
  void add(int i, T x) {
    ++i;
    assert(i > 0);
    while (i <= n) {
      a[i] += x;
      i += i & -i;
    }
  }
  T sum(int i) const {
    T res = 0;
    while (i > 0) {
      res += a[i];
      i -= i & -i;
    }
    return res;
  }
  T range_sum(int low, int high) const { return sum(high) - sum(low); }
  T at(int i) const { return sum(i + 1) - sum(i); }
  void assign(int i, T x) { add(i, x - at(i)); }
};
int main() {
  fast_io();
  string s;
  cin >> s;
  const int n = s.size();
  FenwickTree<int> ft(n);
  vector<int> p(n, -1);
  stack<int> left;
  for (int i = 0; i < (int)(n); i++) {
    if (s[i] == '(')
      left.push(i);
    else {
      if (!left.empty()) {
        p[left.top()] = i;
        left.pop();
        ft.add(i, 1);
      }
    }
  }
  int m;
  cin >> m;
  vector<tuple<int, int, int>> q;
  for (int i = 0; i < (int)(m); i++) {
    int l, r;
    cin >> l >> r;
    --l, --r;
    q.emplace_back(l, r, i);
  }
  sort((q).begin(), (q).end());
  vector<int> res(m);
  int t = 0;
  for (auto& it : q) {
    int l = get<0>(it), r = get<1>(it), qi = get<2>(it);
    while (t < l) {
      if (s[t] == '(' && p[t] != -1) ft.add(p[t], -1);
      ++t;
    }
    res[qi] = 2 * ft.sum(r + 1);
  }
  for (int i = 0; i < (int)(m); i++) cout << res[i] << endl;
}
