Consider numbers \(2, 3, 4, ..., N\) (the first \(N\) positive integers except \(1\)). You want to color them in such a way that there is no triple of (not necessarily distinct) same-colored numbers \(a, b, c\) such that \(a \cdot b = c\).

What is the minimum number of colors you can use?

Input

The first line contains the integer \(N\).

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

Output

In the first line print the minimum possible number of colors used.

In the second line print \(N - 1\) numbers-- the coloring of numbers \(2, 3, ..., N\) in your solution. Colors should be consecutive integers starting from \(1\). If there are multiple optimal colorings, print any of them.

Example

Input 1:

3

Output 1:

1
1 1

Input 2:

4

Output 2:

2
1 2 2

Explanation

Input 1: It is possible to color both \(2\) and \(3\) with the same color, thus using only one color, which is the minimum possible.

Input 2: One can't color numbers \(2\) and \(4\) with the same color, as \(2 \cdot 2 = 4\). Note that colorings \(2\) \(2\) \(1\), \(2\) \(1\) \(1\), and \(1\) \(1\) \(2\) (and only them) will be accepted as well.