406983: GYM102646 A2 Product of Triples (Hard Version)

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A2. Product of Triples (Hard Version)time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Many great mathematicians have sequences named after them. Timmy is a great mathematician, so he created a sequence called $$$t$$$, but he needs help to compute its values. Let $$$t_i$$$ be the number of unordered triples $$$(a, b, c)$$$ where $$$a \leq b \leq c$$$ and $$$a \cdot b \cdot c = i$$$. For all $$$i$$$ from $$$1$$$ to $$$n$$$, find and print $$$t_i$$$.

Input

The only line contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^4)$$$.

Output

For all $$$i$$$ from $$$1$$$ to $$$n$$$, print $$$t_i$$$.

ExampleInput
10
Output
1
1
1
2
1
2
1
3
2
2
Note

There are $$$3$$$ triples that have product $$$8$$$: $$$(1, 1, 8)$$$, $$$(1, 2, 4)$$$, and $$$(2, 2, 2)$$$. However, there is only $$$1$$$ triple that has product $$$7$$$: $$$(1, 1, 7)$$$.

加入题单

上一题 下一题 算法标签: