Boolean Postfix

Interview

Time limit1sMemory limit256 MB

Summary

Evaluate each postfix Boolean formula with AND, OR, XOR, and NOT using a stack and print 1 for true and 0 for false.

Level: Easy3 of 10
Topics: Stack
Solved: No attempts yet

Problem

Logical Boolean expressions are usually written in infix notation, with the operators (∧, ∨) placed between their operands. For example, ((a∧b)∨¬c) is true when a and b are both true, or when c is false. Mary Lucy Margret writes the operator after its operands instead, which is called postfix notation. In her notation the same expression becomes (a b ∧ c ¬ ∨).

Write a program that parses and evaluates Boolean expressions written in Mary Lucy Margret's postfix notation. Every expression you are given is a correct and valid one.

Input

The first line contains one integer $T$ , the number of expressions. Each of the next $T$ lines contains one Boolean formula in postfix notation. The line starts with an integer $n$ , the number of tokens, followed by the $n$ tokens, each separated by a single space.

The tokens 1 and 0 denote the Boolean values true and false. Uppercase letters denote the operators. The possible tokens are:

1 for Boolean true,
0 for Boolean false,
A for logical and,
R for logical or,
X for logical exclusive or,
N for logical negation.

Output

Print $T$ lines. Each line contains 1 if the corresponding expression evaluates to true, and 0 otherwise.

Examples5

Example 1

Input

3
3 0 1 R
3 0 0 R
7 1 0 A 1 R N N

Expected output

1
0
1

Example 2

Input

4
9 0 0 A 0 N 0 N A R
9 0 1 A 0 N 1 N A R
9 1 0 A 1 N 0 N A R
9 1 1 A 1 N 1 N A R

Expected output

Example 3
Input
```
2
1 1
1 0
```
Expected output
```
1
0
```

Example 4

Input

Expected output

Example 5

Input

4
2 1 N
2 0 N
5 1 N N N N
4 0 N N N

Expected output