Задачі
T1. Калькулятор EТ
T1. Калькулятор EТ
Калькулятор Ильи выполняет два действия: умножает текущее число на 3 и прибавляет к нему 1. На калькуляторе сейчас число 1. Помогите Илье определить наименьшую последовательность действий, после которой он получит число n.
Входные данные
Одно число n (1 ≤ n ≤ 109
).
Выходные данные
Выведите в одной строке искомую последовательность действий как показано в примере. Выводите 1, если добавляете единицу. Выводите 3, если умножаете на три.
Пояснение
В первом примере числа на экране калькулятора могут меняться соедуюшим образом:
1 → 2 → 6 → 7 → 8 → 24 → 25 → 26
Можно убедиться, что это самый короткий путь получить число 26.
Вхідні дані #1
26
Вихідні дані #1
1311311
Вхідні дані #2
1447
Вихідні дані #2
3113113113131131