DECSUMS - Sums Decompositions

no tags 

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


hide comments

Added by:legrand
Date:2013-09-13
Time limit:1s-8s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:general