eolymp
bolt
Try our new interface for solving problems
Problems

T1. Calculator EТ

T1. Calculator EТ

Time limit 1 second
Memory limit 128 MiB

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 (1n10^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:

12678242526

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