质数

【题目描述】

将$1\sim n$共$n$个自然数分成尽可能少的集合，使得每个集合的元素和均为质数。

【输入】

一行一个正整数$n$。

【输出】

第一行一个正整数$cnt$表示最少集合数。 第二行$n$个$[1,cnt]$中的用空格隔开的整数，其中第$i$个数$x$表示自然数$i$在第$x$个集合中，若有多种方案输出任意一中即可。 若无解输出$-1$。

【输入样例】

8

【输出样例】

2
1 2 2 1 1 1 1 2

【提示】

【数据规模】 对于30%的数据，$n≤20$。 对于100%的数据，$n≤6000$。