Arithmetic Expression Evaluation Problem Statement

You are provided with a string expression consisting of characters '+', '-', '*', '/', '(', ')' and digits '0' to '9', representing an arithmetic expression in infix notation. Your task is to evaluate this arithmetic expression.

Explanation

In infix notation, operators are placed between their operands.

Note:

1. The '/' operator is considered as floor division.
2. The '*' and '/' operators have higher precedence than '+' and '-'.
3. The string expression always starts with '(' and ends with ')'.
4. It is assured that 'expression' represents a valid infix expression.
5. There will be no division by zero cases.
6. No other characters than the specified ones are present in the string.
7. The operands and final result will fit in a 32-bit integer.

Input

The first line of input contains an integer ‘T’ indicating the number of test cases.
The next T lines each contain a string ‘expression’ representing a test case.

Output

For each test case, output an integer on a new line representing the evaluated value of the arithmetic expression.

Example

Input:
2
((2+3)*(5/2))
((1+2)*(3-1))

Output:
10
6

Constraints

• 1 ≤ T ≤ 50
• 3 ≤ |expression| ≤ 104
• Time limit: 1 sec