Boolean Postfix

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.

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.

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