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)
def fact(n):
    if(n<=1):
        return 1
    else:
        return fact(n-1)*n
t=input()
while t:
    t=t-1
    r=len(raw_input().strip())-1
    print fact(2*r)/(fact(r)*fact(r+1))