Remote Training on Programming

Дано натуральное число N, не превосходящее 1000. За один ход разрешается поделить его на 2 или на 3 (если делится нацело) либо вычесть 1. Определите, за какое минимальное число ходов можно получить единицу, а также сами эти ходы.

Input

Одно натуральное число N, меньшее или равное 1000

Output

В первой строке выведите натуральное число K - минимальное число ходов.

В следующей строке выведите через пробел K чисел 1, 2 или 3, где 1 означает вычитание единицы, 2 - деление на 2, 3 - деление на 3. Если есть различные правильные ответы, выведите любой.

Sample

5

3
1 1 3