While evaluating a expression of N distinct factors i.e (A1 * A2 * ..... * An) , Chef wanted to know in how may ways this expression can be evaluated by parenthesizing two factors at a time.

Input
The first line of the input contains an integer T denoting the number of test cases, for each test case enter the string with N distinct factors (eg xyz , qwerty ,etc)

Output
For each test case, output a single line with number of ways to evaluate the given expression.

Constraints

1 ≤ T ≤ 50
1 ≤ N ≤ 34

Example
Input:
2
ghjk
ab
Output:
5
1

Explanation
Case 1 : expression ghjk can be evaluated in 5 ways i.e ((gh)j)k) , (g(h(jk)) , (g((hj)k)) , ((g(hj))k) & ((gh)(jk))
Case 2 : expression ab can be evaluated in single way i.e. (ab)

见题面

见题面