E. Infinite Parenthesis Sequence
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

BaoBao has just found a sequence A = a0, a1, ..., an - 1 of length n in his left pocket. Each element ai in this sequence is either a left parenthesis '(' or a right parenthesis ')'. As BaoBao dislikes short sequences, he decides to make the sequence infinitely long!

Let's denote bi as the element in the i-th position of the infinite parenthesis sequence B. As B is an infinite sequence, i can be positive, zero, or even negative! To derive B from A, one can use the following equations:

As BaoBao is bored, he also crafts a generator to generate an infinite number of parenthesis sequences from sequence B! Denote Bk (k ≥ 1) as the k-th infinite sequence generated by the generator and bki as the element in the i-th position of sequence Bk. For completeness, we define B0 = B. One can derive Bk from Bk - 1 using the following equations:

To obtain a deeper insight of the sequence, BaoBao would like to calculate the number of left parenthesis '(' in the continuous subsequence bkl, bkl + 1, bkl + 2, ..., bkr - 1, bkr of Bk. Please write a program to help him calculate the answer.

Input

There are multiple test cases. The first line of the input contains an integer T, indicating the number of test cases. For each test case:

The first line contains a string s (1 ≤ |s| ≤ 105, ) indicating the sequence A. The i-th character si in s indicates the value of ai - 1.

The second line contains an integer q (1 ≤ q ≤ 105), indicating the number of queries.

For the following q lines, each line contains three integers k, l and r (0 ≤ k ≤ 109,  - 109 ≤ l ≤ r ≤ 109), indicating a query.

It's guaranteed that neither the sum of |s| nor the sum of q of all test cases will exceed 106.

Output

For each query output one line containing one integer, indicating the number of left parenthesis '(' in the continuous subsequence bkl, bkl + 1, bkl + 2, ..., bkr - 1, bkr of Bk.

Example
Input
3
(())
3
0 -3 2
1 -2 3
2 0 0
))()(
3
0 -3 4
2 1 3
3 -4 -1
))()(()(
4
1234 -5678 9012
123 -456 789
12 -34 56
1 -2 3
Output
3
3
0
4
1
1
7345
623
45
3
Note

In the following explanation, the value of bk0 is marked in bold and italics.

For the first sample test case, we have B0 =  ...(())(())(())..., B1 =  ...()()()()()()... and B2 =  ...)()()()()()(..., so the answer is 3, 3 and 0.

For the second sample test case, we have B0 =  ...))()())()())()(..., B1 =  ...())()())()())()..., B2 =  ...)())()())()())(... and B3 =  ...()())()())()())..., so the answer is 4, 1 and 1.