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.*;
import java.util.*;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;
public class Main{
 
//left right is for query range
public static void build(char a[], Node seg[], int start, int end, int cur){
  if(start>end)
  return;
  if(start==end){
    
    if(a[start]==')')
    seg[cur].close++;
    else
    seg[cur].open++;
    return;
  }
  int mid=start+(end-start)/2;
  build(a, seg, start, mid, 2*cur+1);
  build(a,seg, mid+1, end, 2*cur+2);
  long newsubs=Math.min(seg[2*cur+1].open,seg[2*cur+2].close);
  seg[cur].subs=seg[2*cur+1].subs+seg[2*cur+2].subs+newsubs;
  seg[cur].open=seg[2*cur+1].open+seg[2*cur+2].open-newsubs;
  seg[cur].close=seg[2*cur+1].close+seg[2*cur+2].close-newsubs;
  
}
public static Node query( int left, int right, int start, int end, int cur, Node seg[] ){
  if(start>end)
  return new Node(0,0,0);
  if(left>end||right<start)
    return new Node(0,0,0);
  if(left<=start&&right>=end)
    return seg[cur];
  int mid=start+(end-start)/2;
   Node a=query(left,right,start, mid, 2*cur+1, seg);
   Node b=query( left, right, mid+1, end, 2*cur+2, seg);
   Node c=new Node(0,0,0);
    long newsubs=Math.min(a.open,b.close);
    c.subs=a.subs+b.subs+newsubs;
    c.open=a.open+b.open-newsubs;
    c.close=a.close+b.close-newsubs;
    return c;
}



public static void main(String[] args){
    FastReader sc=new FastReader();
    StringBuilder sb=new StringBuilder();
    String str=sc.next();
    char s[]=str.toCharArray();
    int len=str.length();
    Node seg[]=new Node[4*len];
    for(int i=0;i<4*len;i++)
    seg[i]=new Node(0,0,0);
    build(s, seg, 0, len-1, 0);
    int q=sc.nextInt();
    for( int i=0;i<q;i++){
        int l=sc.nextInt();
        int r=sc.nextInt();
        l--;
        r--;
        sb.append(2*(query(l, r, 0, len-1, 0, seg)).subs);
        sb.append("\n");
        
    }
    System.out.println(sb.toString());
    
}

























  static class FastReader{
      BufferedReader br;
      StringTokenizer st;
      public FastReader()
      { br = new BufferedReader(new InputStreamReader(System.in));
      }String next()
      { while (st == null || !st.hasMoreElements()){ try
      { st = new StringTokenizer(br.readLine()); }
      catch (IOException  e){e.printStackTrace();}}
      return st.nextToken();}
      int nextInt()
      {return Integer.parseInt(next());}
      long nextLong(){ return Long.parseLong(next()); }
      double nextDouble(){return Double.parseDouble(next());
      }String nextLine(){ String str = "";
      try{str = br.readLine();}
      catch (IOException e) {e.printStackTrace();}
      return str;}
    }


}
class Node{
  long subs, open ,close;
  Node( long subs, long open, long close){
    this.subs=subs;
    this.open=open;
    this.close=close;
  }
}
