Имеется калькулятор, который выполняет следующие операции:

• умножить число X на 2;
• умножить число X на 3;
• прибавить к числу X единицу.

Определите, какое наименьшее количество операций требуется, чтобы получить из числа 1 число N.

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

Во входном файле написано натуральное число N, не превосходящее 106.

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

В первой строке выходного файла выведите минимальное количество операций. Во второй строке выведите числа, последовательно получающиеся при выполнении операций. Первое из них должно быть равно 1, а последнее N. Если решений несколько, выведите любое.