English

Given a suffix expression with positive integer terms and three operators +, -, *. Calculate the value of the suffix expression.

For example, the suffix expression: 2 3 4 + * 5 - 2 2 * + has a value of 13.

Input

The first line is the number of test cases T of the problem (1 <= T <= 100)

Each test case is given on a line representing a suffix expression, each term being a positive integer in the range 1 to 100. Between two terms, or between two operators, or between a term and an operator, there is one space. Expression length does not exceed 200 characters. Problem data for ensuring suffix expressions are valid. In the calculation process, make sure that the absolute value of intermediate values does not exceed 10⁹.

Output

Each test case is printed on one line, starting with the character '#', followed by the test case number, followed by a space, and finally the result of evaluating the expression.

Example

Input:
1
2 3 4 + * 5 - 2 2 * +

Output:
#1 13

Vietnamese

Cho một biểu thức hậu tố với số hạng là các số nguyên dương và ba toán tử +, -, *. Hãy tính giá trị của biểu thức hậu tố.

Ví dụ: biểu thức hậu tố: 2 3 4 + * 5 - 2 2 * + có giá trị là 13.

Input

Dòng đầu tiên là số testcase T của bài toán (1 <= T <= 100)

Mỗi testcase được cho trên một dòng thể hiện biểu thức hậu tố, mỗi số hạng là một số nguyên dương trong phạm vi từ 1 đến 100. Giữa hai số hạng, hoặc giữa hai toán tử, hoặc giữa số hạng và toán tử, cách nhau một khoảng trắng. Chiều dài biểu thức không quá 200 ký tự. Dữ liệu đề bài cho đảm bảo biểu thức hậu tố là hợp lệ. Trong quá trình tính toán đảm bảo trị tuyệt đối các giá trị trung gian không vượt quá 10⁹.

Output

Mỗi testcase được in trên một dòng, bắt đầu bằng ký tự '#', tiếp theo là số thứ tự của testcae, tiếp theo là một dấu cách (khoảng trắng), và cuối cùng là kết quả của biểu thức Hậu tố

Example

Input:
1
2 3 4 + * 5 - 2 2 * +

Output:
#1 13