题目描述

夏洛克有了一个新女友（这太不像他了！）。

情人节到了，他想送给女友一些珠宝当做礼物。


他买了 nn 件珠宝，第 ii 件的价值是 i+1i+1，也就是说，珠宝的价值分别为 2,3,…,n+12,3,…,n+1。


华生挑战夏洛克，让他给这些珠宝染色，使得一件珠宝的价格是另一件珠宝的价格的质因子时，两件珠宝的颜色不同。


并且，华生要求他使用的颜色数尽可能少。


请帮助夏洛克完成这个简单的任务。

输入格式

只有一行一个整数 n，表示珠宝件数。1≤n≤1e6

输出格式

第一行一个整数k，表示所使用的颜色数；

第二行n个整数，表示第1到第n件珠宝被染成的颜色。


若有多种答案，输出字典序最小的答案。


请用1到k表示你用到的颜色。

3

2
1 1 2