You are given $n$ integers, each integer is from $1$ to $n$, all of them are pairwise distinct. You have to paint them red and blue (each integer should have exactly one color).

The cost of painting is the number of pairs $(x, y)$ such that $y \bmod x = 0$, $y$ is red and $x$ is blue.

For each $k \in [1, n]$, calculate the maximum cost of painting if exactly $k$ integers should have a red color.

Input

The first line contains one integer $n$ ($2 \le n \le 10^5$).

Output

For each $k \in [1,n]$ print one integer — the maximum cost of painting, if exactly $k$ integers should be red.

见题面 Input 部分

见题面 Output 部分