Имеется калькулятор, который выполняет три операции:
- Прибавить к числу
X единицу.
- Умножить число
X на 2.
- Умножить число
X на 3.
Определите кратчайшую последовательность операций, необходимую для получения из числа 1 заданное число
X.
Входные данные
Программа получает на вход одно число
X, не превосходящее 10
6.
Выходные данные
Выведите строку, состоящую из цифр "1", "2" или "3", обозначающих одну из трех указанных операций, которая получает из числа 1 число X за минимальное число операций. Если возможных минимальных решений несколько, выведите любое из них.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
1 |
|
| 2 |
5 |
121 |
| 3 |
562340 |
3333312222122213312 |