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