Evaluate Reverse Polish Notation Expressions

You are given one or more expressions in Reverse Polish Notation (RPN). In this notation, every operator follows all of its operands. For example, the expression 3 4 + is equivalent to 3 + 4, and can be evaluated to produce 7. The expressions may include the operators +, -, *, and /. When performing division, truncate the result towards zero.

Your task is to evaluate each RPN expression and output the result.

The general evaluation process is as follows: For an expression with tokens separated by spaces, scan from left to right. When an operator is encountered, apply it to the previous two operands (the first popped is the second operand, the next is the first operand), and push the result back to the stack. Continue until the end of the expression.

For any expression, let \(a\) and \(b\) be two operands and an operator \(\oplus\) be applied. The operation is defined as follows: \[ a \oplus b \] with division done using integer division truncating towards zero.

inputFormat

The first line of input contains an integer \(T\), representing the number of RPN expressions. Each of the following \(T\) lines contains a valid RPN expression composed of space-separated tokens (operands and operators).

outputFormat

For each RPN expression, output the evaluated result on a new line. Note that division should be truncated towards zero.

## sample

3
3 4 +
5 1 2 + 4 * + 3 -
15 7 1 1 + - / 3 * 2 1 1 + + -

7
14
5

</p>