Задача №2968. Калькулятор с восстановлением ответа

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

  1. Прибавить к числу X единицу.
  2. Умножить число X на 2.
  3. Умножить число X на 3.

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

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

Программа получает на вход одно число N, не превосходящее 106.

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

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

Пример

Ввод Вывод 
1
 

5
 
121
 
562340
 
3333312222122213312
Сдать: для сдачи задач необходимо войти в систему