Evaluate Arithmetic Expressions

You are given T arithmetic expressions. Each expression is a string consisting of non-negative integers and the operators +, -, *, and /, as well as parentheses ( and ). Your task is to evaluate each expression according to the standard operator precedence rules and output the result of each evaluation.

Note that division should be performed with truncation towards zero. For example, the expression 3+5*2 evaluates to 13, and 10/2-1 evaluates to 4.

Formally, you are to implement an algorithm that evaluates an arithmetic expression. The operator precedence is defined as:

\( +, - : 1 \) and \( *, / : 2 \). Parentheses \( ( \) and \( ) \) can override the precedence.

inputFormat

The first line contains an integer \( T \) representing the number of arithmetic expressions. Each of the next \( T \) lines contains one expression string.

It is guaranteed that each expression is valid and contains only non-negative integers and the operators +, -, *, /, and parentheses ( and ). There are no spaces in the expressions.

outputFormat

Output \( T \) lines. The \( i\)-th line should contain the result of evaluating the \( i\)-th expression from the input.

## sample

1
3+5*2

13

</p>