Калькулятор

Є калькулятор, який виконує наступні операції:

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

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

• додати до числа X одиницю.

Визначте, яку найменшу кількість операцій потрібно, щоб отримати з числа 1 число N.

Вхідні дані

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

Вихідні дані

У першому рядку вихідного файлу виведіть мінімальну кількість операцій. У другому рядку виведіть числа, які послідовно отримуються при виконанні операцій. Перше з них повинно бути рівним 1, а останнє N. Якщо розв'язків декілька, виведіть довільний.

Приклади