Калькулятор

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

• умножить число X на 2;

• умножить число X на 3;

• прибавить к числу X единицу.

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

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

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

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

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

Примеры