NATALIAS - Natalia Has Another Problem

no tags 

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 s0s1s2 ... sn-1 (1 ≤ N ≤ 100). It is guaranteed that the ith 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

hide comments
Bhavik: 2014-04-10 14:14:23

i love these kind of questions:))
Ac at first go

Rishabh Dugar: 2013-08-18 05:13:22

phew,,100th,..:)

Parshant garg: 2013-08-16 12:24:18

stuck in 5th case....

Palash: 2013-08-15 16:37:22

@Vishal any unusual cases??

Parshant garg: 2013-08-15 15:19:48

id: 9844920 please check this..

Parshant garg: 2013-08-15 13:48:37

@kojak_ please tell me any extreme test case.. i m not getting that case..
program is running on my system my ans ID: 9844013

Vishal Sharma: 2013-08-06 17:53:45

abe ye to class mein hume assignment diya tha haha


Added by:kojak_
Date:2012-09-18
Time limit:1s-1.183s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Roberto Abreu's Repository