Given an arithmetic expression in Reverse Polish Notation (Postfix Notation), evaluate the value.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Note: a/b should return an integer. It is guaranteed that for any division, the divisor won't be 0.

Examples

Expression: ["6", "3", "+", "5", "/"]
Answer: 1
Explanation: ((6 + 3) / 5) => 9/5 => 1

Expression: ["6", "-3", "+", "5", "-"]
Answer: -2
Explanation: ((6 + -3) - 5) => 3 - 5 => -2

Expression: ["6", "3", "2", "+", "*", "5", "/"]
Answer: 6
Explanation: ((6 * (3 + 2)) / 5) => 6*5/5 => 6

Testing

Input Format

The first line contains an integer ‘T’, denoting the number of test cases.

For each test case the input has two lines:

• An integer ‘n’ denoting the length of the array.
• n space-separated strings denoting elements of the expression array.

Output Format

For each test case, a line containing an integer representing the answer.

Sample Input

3
5
6 3 + 5 /
5
6 -3 + 5 -
7
6 3 2 + * 5 /

Expected Output

1
-2
6

Constraints

1 <= T <= 100

1 <= n <= 104

-200 <= tokensi <= 200