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.Scanner;

public class C {

    final static Segment OPEN = new Segment( 0, 1, 0, 0 );
    final static Segment CLOSE = new Segment( 0, 0, 1, 0 );
    
	public void solve() throws IOException {
        char[] c = in.readLine().toCharArray();
        int n = c.length;
        int n2 = 1;
        while ( n2 < n ) {
            n2 *= 2;
        }
        Segment[] s = new Segment[n2];
        for ( int i = 0; i < n; i ++ ) {
            if ( c[i] == '(' ) {
                s[i] = new Segment( 0, 1, 0, i + 1 );
            } else {
                s[i] = new Segment( 0, 0, 1, i + 1 );
            }
        }
        for ( int i = n; i < n2; i ++ ) {
            s[i] = new Segment( 0, 1, 0, i + 1 );
        }
        // ())( ())( ())(
        for ( int step = 1; step < n2; step *= 2 ) {
            for ( int i = 0; i < n2; i += step * 2 ) {
                s[i] = s[i].merge( s[i + step] );
            }
        }
        int q = Integer.valueOf( in.readLine() );
        for ( int i = 0; i < q; i ++ ) {
            String[] str = in.readLine().split( " " );
            int l = Integer.valueOf( str[0] ) - 1;
            int r = Integer.valueOf( str[1] );
            Segment res = null;
            while ( l < r ) {
                if ( s[l].next <= r ) {
                    if ( res == null ) {
                        res = s[l];
                    } else {
                        res = res.merge( s[l] );
                    }
                    l = s[l].next;
                } else {
                    Segment single = Segment.getSingle(l >= n ? '(' : c[l]);
                    if ( res == null ) {
                        res = single;
                    } else {
                        res = res.merge( single );
                    }
                    l ++;
                }
            }
            out.println( res.pairs * 2 );
        }
	}
    
    private static class Segment {
        int pairs;
        int open;
        int close;
        int next;
        
        Segment( int p, int o, int c, int n ) {
            pairs = p;
            open = o;
            close = c;
            next = n;
        }
        
        static Segment getSingle( char c ) {
            if ( c == '(' ) {
                return OPEN;
            } else {
                return CLOSE;
            }
        }
        
        Segment merge( Segment s ) {
            int p =  pairs + s.pairs;
            int match = Math.min( open, s.close );
            p += match;
            int o = open + s.open - match;
            int c = close + s.close - match;
            return new Segment( p, o, c, s.next );
        }
    }

	public BufferedReader in;

	public PrintWriter out;

	C() throws IOException {
		in = new BufferedReader( new InputStreamReader( System.in ) );
		out = new PrintWriter( System.out );
	}

    void check( boolean f, String msg ) {
        if ( ! f ) {
            out.close();
            throw new RuntimeException( msg );
        }
    }

    void close() throws IOException {
		out.close();
	}

    public void run() throws IOException {
        try {
            solve();
        } catch ( Exception e ) {
            e.printStackTrace();
        } finally {
            close();
        }
    }

    public static void main( String[] args ) throws IOException {
        new C().run();
    }
}
