T1. Калькулятор EТ

Калькулятор Ильи выполняет два действия: умножает текущее число на 3 и прибавляет к нему 1. На калькуляторе сейчас число 1. Помогите Илье определить наименьшую последовательность действий, после которой он получит число n.

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

Одно число n (1 ≤ n ≤ 10^9).

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

Выведите в одной строке искомую последовательность действий как показано в примере. Выводите 1, если добавляете единицу. Выводите 3, если умножаете на три.

Примеры

Примечание

В первом примере числа на экране калькулятора могут меняться соедуюшим образом:

1 → 2 → 6 → 7 → 8 → 24 → 25 → 26

Можно убедиться, что это самый короткий путь получить число 26.