整数的划分

Time Limit: 1000 ms

Memory Limit: 65535 ms

[显示标签]

Description

将一个整数n表示成一系列的正整数之和:
        n = n1 + n2 + n3……+nk(n1 >= n2 >= n3 >= …… >= nk >= 1 ,k >= 1)
被称做正整数n的一个划分。一个正整数n可能存在着不同的划分,例如正整数6的全部划分为:
       6=6;
       6=5+1;
       6=4+2   6=4+1+1;
       6=3+3   6=3+2+1  6=3+1+1+1;
       6=2+2+2 6=2+2+1+1  6=2+1+1+1+1;
       6=1+1+1+1+1+1
则6的划分数为11.

Input

第一行输入N,N为总测试数的个数(N <= 50); 接下来有N行,每行输入一个测试数n,(1 =< n <= 50)。

Output

输出N行,每行为n的划分数。

Sample Input

5
1
5
6
20
25

Sample Output

1
7
11
627
1958

Hint

Source

刘铁俊

提交代码