Persistence

As you may know from previous problems, when she is bored, Eli takes some non-negative integer, splits it into digits, multiplies the digits, and gets a new number. For example, choosing 42 gives 8, choosing 666 gives 216, and choosing 1337 gives 63.

The girl noticed that she can do the same to the result of the number she chose. For example, starting with 1337, she gets 63, whose digits she can also multiply to get 6 * 3 = 18. She can go even further, getting 1 * 8 = 8. When she reaches a single-digit number, the girl stops, since there is nothing more to do.

Eli calls the "persistence" of a number the number of iterations of the above procedure needed to reach a single-digit number. For example, the persistence of 3 is zero (it is already single-digit), the persistence of 42 is 1 (after one iteration it becomes 8), and the persistence of 666 and 1337 is 3 (666 ⇒ 216 ⇒ 12 ⇒ 2 and 1337 ⇒ 63 ⇒ 18 ⇒ 8).

Suddenly Eli wondered which is the smallest number with a given persistence. For example, although 666 and 1337 have persistence 3, the smallest number with that persistence is actually 39 (39 ⇒ 27 ⇒ 14 ⇒ 4). Now the girl asks you to find the smallest number having a given persistence P.

A single line of the standard input contains one integer P, the persistence Eli is interested in.

On a single line of the standard output, print one non-negative integer: the smallest one that has persistence P.

• 0 ≤ P ≤ 11
• The answer is guaranteed to be smaller than 1018.

All natural numbers smaller than 68889 have persistence 6 or less.