For any number N, it is possible to decompose N as the sum of one or more positive numbers. The order of the numbers doesn't matter.

You have to compute the number of decompositions for each number N.

Input

The first line of input contains an integer T, the number of test cases (T < 20). T test cases follow.

Each test case consists of a single integer N (1 <= N <= 120).

Output

For each test case you have to output a single line containing the answer for the task.

Example

Input:
2
2
5
 
Output:
2
7

Decompositions for the second test case:

• 5
• 4 + 1
• 3 + 2
• 3 + 1 + 1
• 2 + 2 + 1
• 2 + 1 + 1 + 1
• 1 + 1 + 1 + 1 + 1