T1. Calculator EТ

Ilya's calculator does two things: multiply the current number by 3 and add 1 to it. The calculator now has the number 1. Help Ilya to find the smallest sequence of operations to get the number n.

Input

One integer n (1 ≤ n ≤ 10^9).

Output

Print in one line the required sequence of operations as shown in the example. Print 1 if you add one. Print 3 if you multiply by three.

Examples

Note

In the first example, the numbers on the calculator screen can change in the following way:

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

You can see that this is the shortest way to get the number 26.