ascode.org discuss3

Description

수식을 표현할 때 연산자의 위치에 따라 전위, 중위, 후위로 나뉜다. 전위는 + 1 2, 중위는 1 + 2, 후위는 1 2 + 와 같은 수식을 말한다.

한 수식이 후위표기법으로 주어졌을 때, 이 수식이 올바른 후위 표기식인지 아닌지를 판단하고, 올바른 후위식인 경우에는 그 계산 결과를 산출하는 프로그램을 작성하시오. 아래는 올바른 후위표기식과 잘못된 후위표기식의 예이다.

5 8 + 8 2 + - : 3
5 4 + - : Incorrect Expression!

Input

첫 줄에 테스트케이스 개수 T(1 <= T <= 10)가 입력된다.
그 다음 줄부터 후위식의 항 수를 나타내는 정수 n(3 <= n <= 20)과 공백으로 구별되는 n개의 항(연산자, 피연산자)으로 구성된 후위식이 한 줄로 입력되며, 이러한 줄이 T개 만큼 입력된다.
후위식에서 사용되는 모든 피연산자는 정수 -1,000과 1,000 사이의 값이다.
입력되는 연산자는 덧셈, 뺄셈, 곱셈, 나눗셈을 의미하는 +, -, *, /(몫) 만 입력된다. 또한 0으로 나누는 경우는 입력되지 않는다.

Output

각 테스트케이스에 대하여 후위식이 올바른 경우에만 그 계산 결과값을 한 줄에 하나씩 출력하고, 잘못된 후위식인 경우에는 Incorrect Expression! 이라고 출력한다.
단, 모든 계산 결과는 정수로만 산출한다.

Sample Input Copy

3
3 3 4 -
7 51 883 + -83 21 + -
4 3 4 2 *

Sample Output Copy

-1
996
Incorrect Expression!

HINT