B. Шерлок и его девушка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Шерлока новая девушка (так необычно для него!). Приближается День Святого Валентина, и он хочет подарить ей украшения.

Шерлок купил n украшений. Цена i-го украшения равняется i + 1, то есть цены украшений равны 2, 3, 4, ... n + 1.

Ватсон поставил перед Шерлоком задачу раскрасить эти украшения так, чтобы два украшения имели разный цвет, если цена одного из них является простым делителем цены другого. Кроме того, Ватсон хочет, чтобы Шерлок использовал как можно меньше различных цветов.

Помогите Шерлоку выполнить это простейшую задачу.

Входные данные

Единственная строка содержит одно целое число n (1 ≤ n ≤ 100000) — количество украшений.

Выходные данные

В первую строку выведите одно целое число k — минимальное число цветов, которое необходимо использовать.

Во вторую строку выведите n целых чисел (в диапазоне от 1 до k), которые задают цвета каждого украшения в порядке увеличения цены.

Если есть несколько способов раскрасить украшения используя k цветов, выведите любой из них.

Примеры
Входные данные
3
Выходные данные
2
1 1 2
Входные данные
4
Выходные данные
2
2 1 1 2
Примечание

В первом примере мы раскрасили украшения с ценой 2, 3 и 4 в цвета 1, 1, и 2 соответственно.

Т. к. 2 является простым делителем 4, то цвета украшений с ценами 2 и 4 должны быть различными.