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 «()(())(())».
#If FastIO not needed, use this and don't forget to strip
import sys, math
input = sys.stdin.readline

"""
In each subsequence:
-
"""


S = input().strip()
two_pows = set()
"""for i in range(31):
    two_pows.add(pow(2,i))
while len(S) not in two_pows:
    S = S + '('"""
n = len(S)
M = int(input())
class segTree:
    def __init__(self):
        self.a = [0]*(2*n)
        self.b = [0]*(2*n)
        self.c = [0]*(2*n)
    
    def build(self, arr):
        for i in range(n):
            self.a[i+n] = 0
            self.b[i+n] = 1 if arr[i] == '(' else 0
            self.c[i+n] = 1 if arr[i] == ')' else 0
        for i in range(n-1,0,-1):
            to_match = min(self.b[i << 1],self.c[i << 1 | 1])
            self.a[i] = self.a[i << 1] + self.a[i << 1 | 1] + 2*to_match
            self.b[i] = self.b[i << 1] + self.b[i << 1 | 1] - to_match
            self.c[i] = self.c[i << 1] + self.c[i << 1 | 1] - to_match
    def query(self, l, r):  
        left = []
        right = []
        l += n 
        r += n 
        while l <= r: 
            if (l & 1): 
                left.append((self.a[l],self.b[l],self.c[l]))
                l += 1
            if not (r & 1): 
                right.append((self.a[r],self.b[r],self.c[r]))
                r -= 1 
            l >>= 1 
            r >>= 1
        a1 = b1 = c1 = 0
        for a2, b2, c2 in left + right[::-1]:
            to_match = min(b1,c2)
            a1 += a2 + 2*to_match
            b1 += b2 - to_match
            c1 += c2 - to_match
        return a1
tree = segTree()
tree.build(S)
#print(tree)
for m in range(M):
    l, r = [int(s) for s in input().split()]
    l -= 1
    r -= 1
    print(tree.query(l,r))
    

#for _ in range(getInt()):
#print(solve())


#print(time.time()-start_time)