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 M of decompositions for each number N.

Input

The first line of input contains an interger T, the number of testcases (T<20). T testcases follow.

Each testcase consists of a single integer N (1<=N<=120)

Output

For each testcase 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 testcase:
 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1