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.