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>
#pragma comment(linker, "/STACK:256000000")
using namespace std;
const double PI = acos(-1.0);
const int INF = 1000000000;
const int MOD = 1000000007;
string s;
int brut(int l, int r) {
  int left = 0, good = 0;
  for (int i = l; i <= r; ++i) {
    if (s[i] == '(') {
      ++left;
    } else {
      if (left) {
        --left;
        good += 2;
      }
    }
  }
  return good;
}
const int N = 1e6 + 5;
int g_open_left[N], g_good[N], g_left[N];
void unite(int la, int ga, int ra, int lb, int gb, int rb, int& lr, int& gr,
           int& rr) {
  gr = ga + gb + 2 * min(la, rb);
  rr = ra + rb - min(la, rb);
  lr = lb + la - min(la, rb);
}
const int NN = 1e6 * 4 + 5;
int l[NN], r[NN], g[NN];
void build(int node_index, int left, int right) {
  if (left > right) return;
  if (left == right) {
    l[node_index] += (s[left] == '(');
    r[node_index] += (s[left] == ')');
  } else {
    int c = (left + right) / 2;
    build(node_index * 2, left, c);
    build(node_index * 2 + 1, c + 1, right);
    unite(l[2 * node_index], g[2 * node_index], r[2 * node_index],
          l[2 * node_index + 1], g[2 * node_index + 1], r[2 * node_index + 1],
          l[node_index], g[node_index], r[node_index]);
  }
}
void get(int node_index, int left, int right, int cleft, int cright, int& ll,
         int& gg, int& rr) {
  if (cleft > right || cright < left || cleft > cright) {
    ll = 0;
    gg = 0;
    rr = 0;
    return;
  }
  if (left <= cleft && cright <= right) {
    ll = l[node_index];
    gg = g[node_index];
    rr = r[node_index];
    return;
  }
  int c = (cleft + cright) / 2;
  int left_l, left_r, left_g, right_l, right_r, right_g;
  get(node_index * 2, left, right, cleft, c, left_l, left_g, left_r);
  get(node_index * 2 + 1, left, right, c + 1, cright, right_l, right_g,
      right_r);
  unite(left_l, left_g, left_r, right_l, right_g, right_r, ll, gg, rr);
}
int fast(int l, int r) {
  int ll, gg, rr;
  get(1, l, r, 0, s.size() - 1, ll, gg, rr);
  return gg;
}
void init() {
  int left = 0, good = 0;
  for (int i = 0; i < s.size(); ++i) {
    if (i) g_left[i] = g_left[i - 1];
    if (s[i] == '(') {
      ++left;
      ++g_left[i];
    } else {
      if (left) {
        --left;
        good += 2;
      }
    }
    g_open_left[i] = left;
    g_good[i] = good;
  }
  build(1, 0, s.size() - 1);
}
int main() {
  int _start = clock();
  cin >> s;
  init();
  int m;
  cin >> m;
  for (int i = 0; i < m; ++i) {
    int l, r;
    cin >> l >> r;
    --l;
    --r;
    cout << fast(l, r) << endl;
  }
  cerr << endl
       << endl
       << "Time: " << (double)(clock() - _start) / CLOCKS_PER_SEC << endl;
  return 0;
}
