2701 - Sherlock and his girlfriend

通过次数

7

提交次数

11

Time Limit : 1 秒
Memory Limit : 128 MB

N个点,标号2...n-1,给这些点染色,要求若a是b的素因子,则a和b的颜色不同,求一种颜色最少的方案。

Input

一个整数n。

Output

第一行一个整数k,表示最少的染色数。第二行n个整数,表示2...n-1的点被染成的颜色。若有多种答案,输出任意一种。

Examples

Input

3

Output

2
1 1 2

Input

4

Output

2
2 1 1 2

Hint

【数据规模】

15654196436809.png

Source

一本通提高