Natalia has another problem she needs your help with. Do you still have some energies left?

A Logical String is a string that represents a valid boolean expression. It is composed of operators AND, OR and NOT and truth values operands. The boolean expressions are recursive in the sense that operators can have other operators as operands. For example, the following is a list of valid Logical Strings:

T
              T
F
  F
AND(T, T)
OR(T, F)
NOT(T)
AND(OR(T, F), AND(F, F))
AND(AND(AND(OR(T, F), F), F), T)
AND ( AND ( OR ( T,F),OR(F,F)),T)

Please note that there can be several spaces in between objects. However, no space will be in between letters of the names. Therefore, "AND(T,T)" is a valid Logical String but "A     N       D(T,T)" is not.

Given a Logical String, please evaluate it and output its truth value.

Input

The first line contains T (1 ≤ T ≤ 100), the number of test cases. Then there are T lines. Each line contains a string s₀s₁s₂ ... s_n-1 (1 ≤ N ≤ 100). It is guaranteed that the i^th Logical String is valid.

Output

For each Logical String given, output its truth value. If it is true, output T, otherwise output F.

Example

Input:
7
T
F
AND(T, T)
OR(T, F)
NOT(T)
AND(OR(T, F), AND(F, F))
AND(AND(AND(OR(T, F), F), F), T)

Output:
T
F
T
T
F
F
F