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

Работаем командами. Команда создает беседу в вк, где обменивается кодом. Задача считается решенной командой, когда она решена всеми участниками команды.
Продолжительность олимпиады 3 часа (первые две пары).
Разбиение на команды:
1) Советск 2: Алексей Жуйков, Дмитрий Бут, Кирилл Лемтюгов
2) Individuals + CS KvsT: Олег Бабиченко, Александр Кузнецов, Тэдер Ярослав
3) Gymn32: Алла Натяганова, Юлия Кондратович, Иван Ларютин
4) Арина Чеверда
5) Роман Хуснутдинов

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

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

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

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

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

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

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

Пример

Ввод Вывод 
1
 

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