Migrated from Lutece 1699 钟大爷和他的女朋友

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

钟大爷突然就脱单了(^o^)/。
她要放暑假了，所以钟大爷想准备一份礼物给他女朋友。

他买了$n$块钻石，其中第$i$块钻石的价格是$i+1$，所以它们的价格分别是$2，3，4，...n+1$。

但是$cx$大爷想考钟大爷一个有趣问题，他要求$zhong\_wang$给这些钻石涂色，要求

1、如果一个钻石的价格是另一个钻石的价格的质因数，那么它们不能涂成相同的颜色。

2、要求所用颜色的总数尽可能小。

让我们来帮助钟大爷先解决这个有趣的问题吧！

Input

输入一个整型数 $n (1<=n<=100000)$,表示钻石的块数。

Output

第一行输出一个整型数$k$， 表示所用的最少的颜色数。

第二行输出$n$个用空格隔开的数$b_{i}(1<=b_{i}<=k)$，分别表示钻石i所涂成的颜色。

如果颜色涂法不唯一，可以字典序最小的一组。

Samples

3

2
1 1 2

4

2
1 1 2 1

Note

By ProLights

Resources

每周一题div2