Є одна купка, яка спочатку містить ~N~ паличок. Двоє грають у таку гру. Кожен з гравців на кожному своєму ході може забрати з купки деяку кількість паличок (звісно, не більше, чим їх є в купці), причому кількості паличок, які можна забирати, для різних суперників різні: 1-й гравець може забирати або 4, або 8, або 16, або 32 палички, тоді як 2-й – або 2, або 7, або 14. Ніяких інших варіантів ходу нема. Ходять гравці по черзі, пропускати хід не можна. Програє той, хто не може походити. Зверніть увагу: оскільки в цій задачі гравці не можуть забирати 1 паличку, можливі також і ситуації, коли палички ще є, а походити вже не можна. Точніше кажучи, 1-й вже не може ходити не лише коли йому не лишили паличок, але також і коли лишили 1, 2 або 3 палички; 2-й вже не може ходити не лише коли йому не лишили паличок, але також і коли лишили 1 паличку.

Вхідні дані

Єдине ціле число ~N~ (~1\leqslant N\leqslant 12345~) – початкова кількість паличок у купці.

Результати

Перший рядок має містити єдине ціле число, або 1 (якщо перший гравець може забезпечити собі виграш), або 2 (якщо другий). Якщо відповідь з першого рядка 2, то на цьому виведення слід припинити. А якщо відповідь з першого рядка 1, то далі треба вивести також перелік всіх можливих перших ходів першого гравця, після яких другий (при правильній грі першого) вже ніяк не зможе виграти. Цей перелік виводити в такому форматі: вибрати лише потрібні числа з переліку допустимих ходів 4, 8, 16, 32, і записати в другому рядку всі вибрані («виграшні») в порядку зростання через пробіли. Кількість «виграшних ходів» виводити не треба і не можна.

Приклади

Вхід

7

Результат

2

Вхід

10

Результат

1
4

Примітки

У першому тесті, 1-й гравець фактично може забрати лише 4 палички; після цього, у 2-го теж нема вибору (може лише забрати 2 палички), але 2-й походити ще зміг, а 1-й, якому лишається 1 паличка, більше не має ходів і програє.

У другому тесті, у 1-го гравця на першому ході фактично є вибір «забирати 4 чи забирати 8», причому якщо він забере 8, то 2-й забере 2 палички і тим виграє, бо 1-му гравцю нема паличок і тому нема ходів. (Отже, 1-му гравцю не варто забирати 8 на своєму першому ході.) А от якщо 1-й гравець на першому ході здогадається забрати 4 палички (залишиться 6), то у 2-го нема вибору (може лише забрати 2 палички, лишається 4), після чого 1-й гравець може забрати 4 палички і тим виграти, бо 2-му гравцю нема паличок і тому нема ходів.