У Шерлока новая девушка (так необычно для него!). Приближается День Святого Валентина, и он хочет подарить ей украшения.
Шерлок купил n украшений. Цена i-го украшения равняется i + 1, то есть цены украшений равны 2, 3, 4, ... n + 1.
Ватсон поставил перед Шерлоком задачу раскрасить эти украшения так, чтобы два украшения имели разный цвет, если цена одного из них является простым делителем цены другого. Кроме того, Ватсон хочет, чтобы Шерлок использовал как можно меньше различных цветов.
Помогите Шерлоку выполнить это простейшую задачу.
Выходные данные
В первую строку выведите одно целое число k — минимальное число цветов, которое необходимо использовать.
Во вторую строку выведите n целых чисел (в диапазоне от 1 до k), которые задают цвета каждого украшения в порядке увеличения цены.
Если есть несколько способов раскрасить украшения используя k цветов, выведите любой из них.
Примечание
В первом примере мы раскрасили украшения с ценой 2, 3 и 4 в цвета 1, 1, и 2 соответственно.
Т. к. 2 является простым делителем 4, то цвета украшений с ценами 2 и 4 должны быть различными.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
|
2
1 1 2
|
|
2
|
4
|
2
2 1 1 2
|