题目描述

将$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$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。