Arithmetic Expression Evaluator

You are given a set of arithmetic expressions, each of which may contain non-negative integers, the operators \(+, -, *, /\), and parentheses. Your task is to evaluate each expression and output its integer result. The division operator performs integer division with truncation toward zero.

It is recommended to implement a recursive descent parser or a similar approach to handle the order of operations and parentheses correctly.

inputFormat

The input is read from standard input (stdin). The first line contains an integer \(T\), representing the number of test cases. Each of the next \(T\) lines contains a single valid arithmetic expression composed of integers (possibly multiple digits), operators (+, -, *, /), and parentheses.

outputFormat

For each test case, output the evaluated integer result on a separate line to standard output (stdout).

3
3+2*2
(1+(4+5+2)-3)+(6+8)
42

7
23
42