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 «()(())(())».
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/*
 public class _381E {

 }

 */
public class _381E {
  public class SegmentTree {
    int[] st;
    int n;

    public SegmentTree(int n) {
      st = new int[4 * n];
      this.n = n;
    }

    void build(int i, int[] a, int r1, int r2) {
      if (r1 == r2) {
        st[i] = a[r1];
      } else {
        build(i * 2 + 1, a, r1, (r1 + r2) / 2);
        build(i * 2 + 2, a, (r1 + r2) / 2 + 1, r2);

        st[i] = Math.min(st[i * 2 + 1], st[i * 2 + 2]);
      }
    }

    int query(int i, int ra, int rb, int[] a, int r1, int r2) {
      if (ra > r2 || rb < r1) {
        return Integer.MAX_VALUE;
      }

      if (ra >= r1 && rb <= r2) {
        return st[i];
      }

      int p1 = query(i * 2 + 1, ra, (ra + rb) / 2, a, r1, r2);
      int p2 = query(i * 2 + 2, (ra + rb) / 2 + 1, rb, a, r1, r2);

      return Math.min(p1, p2);
    }

    int update(int i, int ra, int rb, int[] a, int ind, int val) {
      if (ra == rb && rb == ind) {
        st[i] = val;
        return st[i];
      }

      if (ra > ind || rb < ind) {
        return st[i];
      }

      int p1 = update(i * 2 + 1, ra, (ra + rb) / 2, a, ind, val);
      int p2 = update(i * 2 + 2, (ra + rb) / 2 + 1, rb, a, ind, val);

      return st[i] = Math.min(p1, p2);
    }
  }

  public void solve() throws FileNotFoundException {
    InputStream inputStream = System.in;

    InputHelper in = new InputHelper(inputStream);

    // actual solution
    String s = in.read();

    int n = s.length();

    int m = in.readInteger();

    int[] a = new int[n];
    int[] b = new int[n];

    if (s.charAt(0) == '(') {
      a[0] = 1;
    }
    for (int i = 1; i < n; i++) {
      b[i] = b[i - 1];
      if (s.charAt(i) == '(') {
        a[i] = a[i - 1] + 1;
      } else {
        if (a[i - 1] > 0) {
          a[i] = a[i - 1] - 1;
          b[i]++;
        }
      }
    }

    SegmentTree st = new SegmentTree(n);

    st.build(0, a, 0, n - 1);

    for (int i = 0; i < m; i++) {
      int l = in.readInteger() - 1;
      int r = in.readInteger() - 1;

      int pva = -1, pvb = -1;
      if (l == 0) {
        pva = pvb = 0;
      } else {
        pva = a[l - 1];
        pvb = b[l - 1];
      }

      int min = st.query(0, 0, n - 1, a, l, r);

      int ans = b[r] - pvb;

      if (min < pva) {
        ans -= (pva - min);
      }

      System.out.println(ans * 2);
    }


    // end here
  }

  public static void main(String[] args) throws FileNotFoundException {
    (new _381E()).solve();
  }

  class InputHelper {
    StringTokenizer tokenizer = null;
    private BufferedReader bufferedReader;

    public InputHelper(InputStream inputStream) {
      InputStreamReader inputStreamReader = new InputStreamReader(inputStream);
      bufferedReader = new BufferedReader(inputStreamReader, 16384);
    }

    public String read() {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          String line = bufferedReader.readLine();
          if (line == null) {
            return null;
          }
          tokenizer = new StringTokenizer(line);
        } catch (IOException e) {
          e.printStackTrace();
        }
      }

      return tokenizer.nextToken();
    }

    public Integer readInteger() {
      return Integer.parseInt(read());
    }

    public Long readLong() {
      return Long.parseLong(read());
    }
  }
}
