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.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.InputMismatchException;
import java.util.List;
import java.util.Scanner;
import java.util.StringTokenizer;



public class ValidniSekvenci {

	class Vertex {
		
		int correct;
		int open;
		int closed;
		
		public Vertex() {
			this.correct = 0;
			this.open = 0; 
			this.closed = 0;
		}
		
		
		
	}
	
	class SegmentTreeAg {
		
		Vertex tree[];
		
		public SegmentTreeAg(String s) {
			
			int n = s.length();
			
			int height = (int) Math.ceil(Math.log(n)/Math.log(2));
			int max_size = 2 * (int) Math.pow(2, height) - 1;
			
			tree = new Vertex[max_size];
					
			build(0, n - 1, 0, s);
			
		}
		
		public Vertex build(int l, int r, int id, String s) {
			
			if(l == r) {
				Vertex v = new Vertex();
				if(s.charAt(l) == '(') {
					v.open++;
				}
				else if(s.charAt(l)  == ')') {
					v.closed++;
				}
				tree[id] = v;
				return tree[id];
				
			}
			
			int mid = (l + r)/2;
			
			Vertex lc = build(l, mid, id * 2 + 1, s);
			Vertex rc = build(mid + 1, r, id * 2 + 2, s);
			
			
			int tmp = Math.min(lc.open, rc.closed);
			
			Vertex v = new Vertex();
			tree[id] = v;
			tree[id].correct = lc.correct + rc.correct + tmp;
			
		
			tree[id].open = lc.open + rc.open - tmp;
			tree[id].closed = lc.closed + rc.closed - tmp;
				
			
			return tree[id];
			
			
		}
		
		public Vertex max (int l, int r, int qs, int qe, int id) {
			
			if( qs <= l && r <= qe) {
				return tree[id];
			}
			
			if(qs > r || qe < l) {
				Vertex v = new Vertex();
				v.closed = 0;
				v.open = 0;
				v.correct = 0;
				return v;
			}
			
			
			int mid = (l + r)/2;
			
			Vertex lc = max(l, mid, qs, qe, id*2 + 1);
			Vertex rc = max(mid + 1, r, qs, qe, id*2 + 2);
			
			int tmp = Math.min(lc.open, rc.closed);
			
			int cr = lc.correct + rc.correct + tmp;
			int opened = lc.open + rc.open - tmp;
			int closed = lc.closed + rc.closed - tmp;
			
			Vertex v = new Vertex();
			v.correct = cr;
			v.open = opened;
			v.closed = closed;
			return v;
			
			
		}
		
		
		
		
		
		
		
		
	}
	
	
	public static void main(String[] args) throws IOException {
		
		
		 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	        StringTokenizer tokenizer;
	        String s = br.readLine();
		
			
		
		int m = Integer.parseInt(br.readLine());
		ValidniSekvenci vs = new ValidniSekvenci();
		
		SegmentTreeAg sg = vs.new SegmentTreeAg(s);
		
		for(int i = 0; i < m ; i++) {
			tokenizer = new StringTokenizer(br.readLine());
			int l = Integer.parseInt(tokenizer.nextToken());
			int r = Integer.parseInt(tokenizer.nextToken());
			
				
			bw.write("" + sg.max(0, s.length() - 1, l -1, r-1, 0).correct * 2);
			bw.newLine();
					
		}

		bw.flush();
		bw.close();
	
		
		
		
		
	
	}
	
	
}

class FastScannerB{
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private SpaceCharFilter filter;

    public FastScannerB(InputStream stream)
    {
        this.stream = stream;
    }

    public int read()
    {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars)
        {
            curChar = 0;
            try
            {
                numChars = stream.read(buf);
            } catch (IOException e)
            {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }

    public int nextInt()
    {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-')
        {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do
        {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public String next()
    {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do
        {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));
        return res.toString();
    }
    
    public String nextLine()
    {
        int c = read();
        StringBuilder res = new StringBuilder();
        do
        {
            res.appendCodePoint(c);
            c = read();
        } while (!isLineEndChar(c));
        return res.toString();
    }    
    
    public double nextDouble() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        double res = 0;
        while (!isSpaceChar(c) && c != '.') {
            if (c == 'e' || c == 'E')
                return res * Math.pow(10, nextInt());
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        }
        if (c == '.') {
            c = read();
            double m = 1;
            while (!isSpaceChar(c)) {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, nextInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                m /= 10;
                res += (c - '0') * m;
                c = read();
            }
        }
        return res * sgn;
    }
    
    public long nextLong() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        long res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }
    
    public boolean isSpaceChar(int c)
    {
        if (filter != null)
            return filter.isSpaceChar(c);
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }
    
    public boolean isLineEndChar(int c)
    {
        if (filter != null)
            return filter.isSpaceChar(c);
        return c == '\n' || c == '\r' || c == -1;
    }

    public interface SpaceCharFilter
    {
        public boolean isSpaceChar(int ch);
    }
}


