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 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

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