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.*;
@SuppressWarnings("unchecked")
public class C223 
{
   static long time = System.currentTimeMillis();
   static StringBuilder seq;
   static long[] segmain;
   static long[] segleft;
   static long[] segright;
   static long[] empty = new long[3];
   static long[][] ret;
   static int count = 0;
   public static void main(String[] args) throws Exception 
   {
      FastReader infile = new FastReader();
      //infile = new FastReader("text.in");
      seq = new StringBuilder(infile.next());
      int N = seq.length();
      long t1 = System.currentTimeMillis()-time;
      segmain = new long[4*N+1];
      segleft = new long[4*N+1];
      segright = new long[4*N+1];
      ret = new long[N*3/2][3];
      long t2 = System.currentTimeMillis()-time;
      update(1, 1, N);
      long t3 = System.currentTimeMillis()-time;
      int M = infile.nextInt();
      StringBuilder str = new StringBuilder();
      for(int x = 0; x < M; x++)
      {
         int l = infile.nextInt();
         int r = infile.nextInt();
         count = 0;
         str.append(query(1, 1, N, l, r)[1]).append("\n");
      }
      System.out.println(str);
      //System.out.println(t1+" "+t2+" "+t3);
      //System.out.println("Time: "+(System.currentTimeMillis()-time));
   }
   public static long[] query(int pos, int left, int right, int ltar, int rtar)
   {
      if(rtar<left||right<ltar)
      {
         return empty;
      }
      if(ltar<=left&&right<=rtar)
      {
         //long[] ret = new long[3];
         ret[count][0] = segleft[pos];
         ret[count][1] = segmain[pos];
         ret[count][2] = segright[pos];
         return ret[count++];
      }
      int middle = (left+right)/2;
      long[] lq = query(2*pos, left, middle, ltar, rtar);
      long[] rq = query(2*pos+1, middle+1, right, ltar, rtar);
      long combine = Math.min(lq[0], rq[2]);
      //long[] ret = new long[3];
      ret[count][0] = lq[0]+rq[0]-combine;
      ret[count][1] = lq[1]+rq[1]+2*combine;
      ret[count][2] = lq[2]+rq[2]-combine;
      return ret[count++];
   }
   public static void update(int pos, int left, int right)
   {
      if(left==right)
      {
         if(seq.charAt(left-1)=='(')
            segleft[pos]++;
         else
            segright[pos]++;
         return;
      }
      int middle = (left+right)/2;
      update(2*pos, left, middle);
      update(2*pos+1, middle+1, right);
      long combine = Math.min(segleft[2*pos], segright[2*pos+1]);
      segmain[pos] = segmain[2*pos]+segmain[2*pos+1]+2*combine;
      segleft[pos] = segleft[2*pos]+segleft[2*pos+1]-combine;
      segright[pos] = segright[2*pos]+segright[2*pos+1]-combine;
   }
}
class FastReader
{
   BufferedReader br;
   StringTokenizer st;

   public FastReader(String file) throws FileNotFoundException
   {
      br = new BufferedReader(new FileReader(file));
   }
   
   public FastReader() throws FileNotFoundException
   {
      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;
   }
}