Read problem statements in [Bengali], [Russian], [Mandarin] and [Vietnamese] as well.

A string S whose characters are one of the following 5: (, ), +, - and ?, is said to be a valid string if one of the following conditions holds:
S = \ ?
S = (x+y), where x and y are valid strings.
S = (x-y), where x and y are valid strings.

For example, strings ?, (?-?), (?+(?-?)) are valid strings, while strings (?-+), ??, (?), ?-?, (?+?)) are not.

The power of a valid string S is defined to be the maximum value attainable by replacing each ? in it by either 0 or 1 and evaluating the resulting expression.

For example, the power of (?-?) is 1 because we can obtain (1 - 0) which evaluates to 1.

You are given a valid string S, and Q queries on it. Each query is represented by two integers L and R (L≤ R).
Your task is to find the power of the substring $S_{L}, S_{L+1}, \dots, S_{R}$. It is guaranteed that this substring is a valid string.

Note: The input of this problem is large, so use fast input/output methods.

------ Input Format ------

• The first line of input contains an integer T, denoting the number of test cases. The description of T test cases follows:
• The first line of each test case contains the string S.
• The next line contains an integer Q, representing the number of queries to answer.
• Each of the following Q lines contains two space-separated integers, L and R, representing the query.

------ Output Format ------

For each test case, print one line containing Q space-separated integers, the i-th of which represents the answer to the i-th query.

------ Constraints ------

$1 ≤ T ≤ 1000$
$1 ≤ |S| ≤ 10^{6}$
$1 ≤ Q ≤ 10^{6}$
$1 ≤ L ≤ R ≤ |S|$
$\sum{|S|}$ and $\sum{Q}$ over all test cases does not exceed $10^{6}$.

------ subtasks ------

Subtask #1 (20 points):
$1 ≤ |S| ≤ 1000$
$1 ≤ Q ≤ 1000$
$\sum{|S|}$ and $\sum{Q}$ over all test case does not exceed $10^{4}$.

Subtask #2 (80 points):
Original constraints

----- Sample Input 1 ------
3
(?+?)
2
2 2
1 5
(?-(?-?))
2
1 9
4 8
(?-(?+?))
1
1 9
----- Sample Output 1 ------
1 2
2 1
1
----- explanation 1 ------
Test case 1:
- Query 1: Power of the string $?$ is $1$, as it can be converted to $1$.
- Query 2: Power of the string $(?+?)$ is $2$, as it can be converted to $(1+1)$.

Test case 2:
- Query 1: Power of the string $(?-(?-?))$ is $2$, as it can be converted to $(1-(0-1))$.
- Query 2: Power of the string $(?-?)$ is $1$, as it can be converted to $(1-0)$.

Test case 3:
- Query 1: Power of the string $(?-(?+?))$ is $1$, as it can be converted to $(1-(0+0))$.

见题面

见题面