Розглянемо 7-значні цілі числа в десятковій системі числення, дозволяючи нулі в старших розрядах. Тобто, числа від 0000000 до 9999999. Над числом дозволено виконувати такі перетворення:

• додати 1 (не застосовне до 9999999);

• відняти 1 (не застосовне до 0000000);

• домножити на будь-яке натуральне число k від 2 до 9 (застосовне тільки коли отриманий добуток не перевищує 9999999);

• поділити на будь-яке натуральне число k від 2 до 9 (застосовне тільки коли число до перетворення кратне k);

• виконати циклічний зсув вліво, тобто стерти найстаршу цифру і дописати її справа (наприклад, 1234567 → 2345671; застосовне до будь-якого числа);

• виконати циклічний зсув вправо, тобто стерти наймолодшу цифру і дописати її зліва (наприклад, 1234567 → 7123456; застосовне до будь-якого числа).

Напишіть програму, яка за двома вказаними 7-значними числами A та B знаходитиме, як перетворити перше у друге за мінімальну кількість кроків.

Вхідні дані

Програма читає з клавіатури (пристрою стандартного введення) початкове та кінцеве значення A та B. Кожне значення складається рівно з 7-ми десяткових цифр, між значеннями знаходиться рівно один пропуск.

Результати

Програма виводить на пристрій стандартного виведення (екран) спочатку мінімальну кількість перетворень M, далі треба вивести M+1 штук 7-цифрових чисел, де перше дорівнює A, останнє дорівнює B, і кожне наступне отримане з попереднього згідно одного з перетворень. Числа, менші ~10^6~, мають бути доповнені нулями до 7-значних. Якщо можливі різні правильні послідовності з однаковою мінімальною кількістю перетворень — виводьте будь-яку одну з них. Числа виводяться через пропуск.

Приклади

Введення 1

3330333 3333033

Виведення 1

1 3330333 3333033

Введення 2

0000000 0370370

Виведення 2

6 0000000 0000001 1000000 0999999 0111111 0037037 0370370