e-olymp
Задачі

Магічна машинка

Магічна машинка

У Ібрагіма є чорна магічна машинка. На ній є три кнопки і табло. Табло може показувати не більше ніж чотирьохзначні числа. Кожна з кнопок міняє число деяким чином: перша домножує його на 3, друга додає до нього суму його цифр, а третя віднімає від нього 2. У випадку, якщо число стає від'єним чи перевищує 9999, машинка ламається.

Ібрагім може натискувати кнопки у довільному порядку. Його цікавить, як йому отримати на табло число b після деякої послідовності натиснень, якщо зараз машинка показує a. Допоможіть йому знайти мінімальну необхідну кількість натиснень.

Вхідні дані

В одному рядку містяться два натуральних числа a та b (1a, b9999).

Вихідні дані

Вивести мінімальну кількість дій, за яку з числа a можна отримати b.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
14 15
Вихідні дані #1
2
Вхідні дані #2
18 12
Вихідні дані #2
3
Вхідні дані #3
14 29
Вихідні дані #3
2