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

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

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

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