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
Ehor Nechiporenko: 2012-08-10 14:12:38

Nice dynamic programming problem

BOND: 2012-05-27 13:31:28

my O/P is same as @:D ...

:D: 2013-01-12 10:50:29

Test cases must be extremely weak. I got AC and my program gives the following:

1
1
2
0
5
37
1
0
2

For example for three arguments number of all ways to parenthesize the expressions is 5.

See this for some reference:
http://en.wikipedia.org/wiki/Catalan_number

Last edit: 2012-05-11 19:38:19
Marcelo: 2012-05-11 00:22:51


Some inputs and outputs.
9
T or F
T xor F
T and T and T
T and F
T or F and T xor F
T or T and F xor T and T or F
T xor T and F
F or F and T
T or T or T

Outputs
1
1
2
0
7
91
1
0
2

Last edit: 2012-05-11 00:29:00
Anirban Saha: 2012-03-09 05:57:23

can you open it for other languages like Java ?

Xusuo J: 2012-03-07 05:09:56

For Tywan, it is 2.

Tywan: 2012-02-02 15:30:16

What is the answer for "T and T and T"? Is it 6?

priyamehtanit : 2012-01-22 09:54:49

yes it does :)

Bharath: 2012-01-22 09:43:57

does the result fit into a long long?

Last edit: 2012-01-22 09:44:12

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