Background

土拨鼠墨墨要过$n$岁生日了, 她希望收到与众不同的礼物

Description

她的男朋友黑黑给她购买了$n$个甜甜圈, 每个甜甜圈上写着一个数字, 第$i$个甜甜圈的数字为$i+1$, 墨墨希望拥有不同口味的甜甜圈, 她希望如果一个甜甜圈的数字是另一个甜甜圈数字的质因子的时候, 两个甜甜圈口味应该不同, 比如$2$是$4$的质因子, 则$2$和$4$的口味应该不同.

现在黑黑想要实现墨墨的愿望, 你能帮黑黑求出最少需要使用多少口味, 以及每种口味的方案.

Format

Input

只有一行一个整数$n$, 表示甜甜圈的数量

Output

第一行一个整数$k$, 表示最少需要多少口味.

第二行$n$个整数, 表示第$i$个甜甜圈的口味, 用数字表示, 如果有多组答案, 输出任意一种.

Samples

3

1 1 2

4

2 1 1 2

样例解释

2是4的质因子, 所以1, 3两个甜甜圈口味必须不同

Limitation

$1 <= n <= 10^5$