Description

후위 연산식이 들어왔을 때 이를 계산하는 프로그램을 작성한다.

주어지는 연산자는 덧셈, 뺄셈, 곱셈이 주어지며, 주어지는 숫자는 1자리의 양의 정수이다.

Input

입력은 여러개의 테스트 케이스로 이뤄진다.

입력의 첫 줄에는 테스트 케이스의 개수 T(1 <= T <= 100)이 주어진다.

테스트 케이스는 한줄로 이뤄지며, 테스트 케이스의 맨 처음에는 테스트 케이스에 주어지는 연산자와 숫자의 개수 N이 주어진다( 1 <= N <= 2000 )

그 다음 부터 N개의 숫자와 연산자가 주어지며, (숫자의 개수) = (연산자의 개수)+1 이 반드시 성립하도록 입력이 주어진다. 다시 말해서 계산이 불가능한 수식은 입력되지 않는다. 숫자는 1, 2, ..., 9 중의 하나의 한자리 숫자이며, 연산자는 '+', '-', '*' 로 주어지며 각각 덧셈, 뺄셈, 곱셈을 뜻한다.

Output

각 테스트 케이스에 대해 후위 표기법으로 입력된 수식의 결과를 출력한다.

5
1 5
3 5 3 +
3 5 3 *
7 1 1 + 1 1 - *
7 1 1 1 1 + + +

5
8
15
0
4

HINT

Java에서 Scanner 를 사용할 경우 연산자, 숫자의 수를 제외하고는 next() method로 입력을 받고,  String의 equals() method를 통해 연산자인지 아닌지를 비교하는 것이 좋다. 

다음은 String으로 입력된 숫자를 int 변수로 변환하는 예시이다.

public class Main {
	public static void main(String args[]) {
		String x = "1234";
		int intVal = Integer.parseInt(x);
		System.out.print(intVal);
	}
}