Minimum Parent Metamorphic Number

Given a positive integer k which represents a child metamorphic number, find the smallest parent metamorphic number n (with at least two digits) such that the product of the digits of n equals k. The transformation is defined recursively as follows:

• If n has more than one digit (ignoring any leading zeros), let its child metamorphic number be the product of its digits, i.e., if n = d_1d_2...d_m then its child is \(m = d_1\times d_2\times\cdots\times d_m\). In this case, the metamorphic number of n is defined to be the metamorphic number of m.
• If n is a single-digit number, then its metamorphic number is n itself.

For example, for n = 679, the chain is illustrated as follows: \[ 679 \to 378 \ (6 \times 7 \times 9) \to 168 \to 48 \to 32 \to 6 \] so the metamorphic number is \(6\).

Now, given a child metamorphic number k, determine the smallest parent metamorphic number n such that the product of its digits equals k. Note that for numbers where k is less than 10, n must still be a two-digit number. In such cases, n is formed by prefixing k with a 1 (with the special case k = 0 resulting in 10).

inputFormat

The input consists of a single line containing a non-negative integer k \( (0 \le k \le 10^9) \).

outputFormat

Output the smallest parent metamorphic number whose digits multiply to k. If no such number exists, output -1.

sample

18

29