355. Numbers Painting

Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Dr. Vasechkin wants to paint all numbers from 1 to N in such a way that if number A is divisible by number B, numbers A and B have different colors.

Help Dr. Vasechkin to find such a painting, where the number of the colors used is minimal.

Input
The input contains integer number N ().

Output
Write the number of the colors M in the desired painting in the first line of the output. In the second line of the output write the desired painting of numbers from 1 to N. The used colors should be represented by numbers from 1 to M. If there are several solutions, choose any of them.

Example(s)
sample input
sample output
12
4
1 2 2 3 2 3 2 4 3 3 2 4




Online Contester Team © 2002 - 2010. All rights reserved.