Sherlock 有了一个新女友（这太不像他了！）。情人节到了，他想送给女友一些珠宝当做礼物。
他买了 n 件珠宝。第 i 件的价值是 i+1 。那就是说，珠宝的价值分别为2, 3, 4.....n+1 。
Watson 挑战 Sherlock，让他给这些珠宝染色，使得一件珠宝的价格是另一件的质因子时，两件珠宝的颜色不同。并且，Watson 要求他最小化颜色的使用数。
请帮助 Sherlock 完成这个简单的任务。
样例1：
3
样例2：
4
样例1：
2
1 1 2
样例2：
2
2 1 1 2
因为 2 是 4 的一个质因子，因此第一件珠宝与第三件珠宝的颜色必须不同。
对于全部数据，1 ≤ n ≤ 10^5。