Background

Special for beginners, ^_^

Description

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

Format

Input

只有一行一个正整数 $n（\le 10^5）$，表示珠宝件数。

Output

第一行一个整数k，表示最少的染色数； 第二行n个整数，表示第1到第n件珠宝被染成的颜色。若有多种答案，输出字典序最小的那种。

Samples

3

2
1 1 2

Limitation

1s, 1024KiB for each test case.