Postfix notation is a kind of expression for mathematic widely used in computer architectures. The meaning of postfix notation is fairly simple and can be concluded as follow:
(1) There are two kinds of token: operators (e.g. “+”, “-“, ”*”, “/”) and operands (values, in other word).
(2) The operators follow their operands. For example, “3 + 4” (infix notation) will be written into “3 4 +”.
(3) If there are multiple operations, the operator is given immediately after its second operand. For example, “3 – 4 + 5” will be written into “3 4 – 5 +”.
The first line of the input contains an integer N (N ≤ 1000) which denotes the number of test cases. Each test case begins with an integer M (M ≤ 10000) representing the number of tokens in the expression, followed by M tokens in the next line. Tokens are separated by spaces and the operators contain only “+”, “-”; the operands are integers in the range [0, 100]. Calculate the result of the expression. You may assume that the given expressions are always valid.
The output of each test case occupies a line. Each line begins with the test case number “Case i:”, and then a space character followed by the evaluated answer.