PAREN - COUNT PAREN

no tags 

You are given a boolean expression consisting of a string of the symbols 'true', 'false', 'and', 'or', and 'xor'. Count the number of ways to parenthesize the expression such that it will evaluate to true.

"and", "or" and "xor" are of the same priority.

Input

An integer t, 1<=t<=100, denoting the number of testcases, followed by t lines, each containing a space separated string consisting of T, F, and, or and xor of length less than 100 characters

Output

For each string given at input, display a line with the number of ways to parenthesize the expression such that it will evaluate to true.

Example

Input:
1
T and F

Output:
0

hide comments
hemant_dhanuka: 2018-05-29 11:52:51

Shit Man, No java

aditya730: 2017-01-11 12:58:27

Test cases seem too be very weak.Should go for a rejudge

Ankit: 2015-08-13 14:06:18

nice problem to implement using dp

Divyank Duvedi: 2014-10-28 23:33:07

test data is weak.....my code gave wrong answer for input string="T"...however it passed the given test data

Divyank Duvedi: 2014-10-28 23:04:50

enjoyed solving this one :)

Mauro Persano: 2013-10-21 03:09:09

There must be something wrong with the test cases... my solution just got accepted, and my output for T or F and T xor F is different from that of Marcelo or :D.

Last edit: 2013-10-21 03:09:43
Akhilesh Anandh: 2013-08-10 14:26:56

Same output as :D :
1
2
0
5
37
1
0
2

Got accepted :)

RAJDEEP GUPTA: 2013-04-09 17:32:41

My output is same as that of zukow.
(Output for T or T and F xor T and T or F is 37)

Abhishek Verma: 2013-03-24 19:34:59

answer for :
T or T and F xor T and T or F
is 59..i got AC
@marcelo - correct your fourth last test case rest is fine

Thotsaphon Thanatipanonda: 2013-03-05 15:02:56

Java please!!


Added by:priyamehtanit
Date:2012-01-21
Time limit:1s-3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C++ 4.3.2 CPP
Resource:mit tutorial