Q33: Split and Merge
We define an operation on an integer, N, code named Split-And-Merge, as follows:
- First, split N into many integers a1, a2, ..., ak such that
N = a1 + a2 + ... + ak
- Next, we merge them into a new integers M by multiplying them together
M = a1 * a2 * ... * ak
Given N <= 1000, how many distinct M can we arrive at by split-and-merging N?
(e.g. N = 5, we can get {1, 2, 3, 4, 5, 6}, a total of 6 distinct values. To get 6, do 2*3)
Submit this problem in the judge as "Q33"
INPUT
There will be multiple test cases, on multiple lines.
Each line will contain an integer 0 <= N <= 1000.
The case N = 0 signifies the end of input.
OUTPUT
For each test case, output the number of distinct M's as described above.
Sample Input
1
2
3
4
5
6
1000
0
Sample Output
1
2
3
4
6
8
2412840866087356219