Evaluate the result of a given numerical expression written in postfix notation.
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 “+”, “-”, “*” and “/”; the operands are integers in the range [0, 100]. The division operator “/” here is considered as integral division.
You may assume the syntax of the expression is always valid. However, the case divided-by-zero may occur. If divided-by-zero operation appears in any stage of the evaluation, output "divided by zero". Otherwise, calculate the result of the expression.
The evaluated results (in each stage of the evaluation) will fit in 32-bit signed integers.
Case 1: 1 ≤ N ≤ 10, 1 ≤ M ≤ 10
Case 2: 1 ≤ N ≤ 300, 1 ≤ M ≤ 100
Case 3: 1 ≤ N ≤ 500, 1 ≤ M ≤ 1000
Case 4: 1 ≤ N ≤ 1000, 1 ≤ M ≤ 10000
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.