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

Калькулятор Іллі може виконувати дві операції: множити поточне число на 3 або додавати до нього 1. Наразі на калькуляторі відображається число 1. Допоможіть Іллі знайти найкоротшу послідовність дій, щоб отримати число n.

Вхідні дані

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

Вихідні дані

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

Приклади

Примітка

У першому прикладі числа на екрані калькулятора можуть змінюватися наступним чином:

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

Це найкоротший шлях для отримання числа 26.