Description

Original problem from: Codeforces Round #400 B.

Sherlock has a new girlfriend (which is very unlike him!). Valentine's Day is approaching, and he wants to give her some jewelry as a gift.

He bought $n$ pieces of jewelry. The value of the $i$-th piece is $i+1$. That is, the values of the jewelry are $2, 3, 4, \cdots, n+1$.

Watson challenges Sherlock to color these pieces such that when the value of one piece is a prime factor of another, the two pieces must have different colors. Additionally, Watson requires him to minimize the number of colors used.

Please help Sherlock complete this simple task.

Input Format

A single integer $n$, representing the number of jewelry pieces.

Output Format

The first line should contain an integer $k$, indicating the minimum number of colors used.
The second line should contain $n$ integers, representing the colors assigned to the $1$-st to the $n$-th piece of jewelry. If there are multiple possible solutions, output any one of them.

Sample 1

3

2
1 1 2

Sample 2

Since $2$ is a prime factor of $4$, the first and third pieces of jewelry must have different colors.

4

2
2 1 1 2

Data Range and Hints

For all data, $1\le n\le 10^5$.