G. Простая задача
ограничение по времени на тест
1 second
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

В Берляндии в моде простые числа — респектабельные горожане селятся только на этажах с номерами, которые являются простыми числами. Нумизматы особо ценят монеты с простыми номиналами. Все простые дни объявлены праздничными!

Но и этого мало, чтобы сделать жителей Берляндии счастливыми. На главной улице столицы стоит n домов, пронумерованных от 1 до n. Правительство решило покрасить каждый дом в некоторый цвет так, что сумма номеров домов покрашенных в каждый из цветов является простым числом.

Однако, оказалось, что не все жители поддерживают это решение — многие против по причине того, что не хотят большого количества разноцветных домов на главной улице столицы. Поэтому решено использовать минимальное количество цветов. Дома не обязательно красить подряд, но каждый из n домов должен быть покрашен в некоторый цвет. Одноцветные дома не обязательно должны идти подряд, допускается любая раскраска.

До начала покраски осталось не более 5-ти часов, помогите правительству найти такой способ, чтобы сумма номеров домов для каждого цвета была простым числом, а количество использованных красок было минимальным.

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

Единственная строка входного файла содержит целое число n (2 ≤ n ≤ 6000) — количество домов на главной улице столицы.

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

Выведите последовательность n чисел, где i-ое число обозначает номер цвета для дома номер i. Цвета нумеруйте последовательно, начиная с 1. Разрешается любой порядок покраски. Если решений несколько, выведите любое. Если такой покраски не существует, то выведите единственное число -1.

Примеры
Входные данные
8
Выходные данные
1 2 2 1 1 1 1 2