Description

题目描述请参考试题册

Input

There are T test cases(2≤T≤200). For each test case, only one line with one integer n. (0<n<200)

Output

For each test case output the number of all situations exists.

Sample

Input

1
2
10
20

Output

1
2
42
627

Hint

Notice that long long or int64 is needed