A2. Product of Triples (Hard Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard 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$$$.

Example
Input
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)$$$.