Description

There are \(N\) stones, numbered \(1,2,...,N\).

There is a frog who is initially on Stone \(x\). He will repeat the following action some number of times to reach Stone \(N\):

• If the frog is currently on Stone \(i\), jump to Stone \(i + d\) or Stone \(i - d\) where \(d\) is a divisor of \(i\).

Here, an integer \(b\) is said to be a divisor of \(a\) if there exist an integer \(c\) such that \(a = b \times c\).

For each starting stone \(1 \leq x \leq N\), find the minimum number of jumps to reach Stone \(N\).

Input

The only line contains an integer \(N\).

\(N\)

Constraints

• \(1 \le N\le 10^6\)

Output

Please output \(N\) integers in a line, each followed by a space.

Sample Input  Download

Sample Output  Download

Tags

Discuss