Problems
T1. Calculator EТ
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 data
One integer n (1 ≤ n ≤ 10^9
).
Output data
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
Input example #1
26
Output example #1
1311311
Input example #2
1447
Output example #2
3113113113131131
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.