Smallest Integer with Given Product of Digits

Given a positive integer \(N\), your task is to find the smallest positive integer \(M\) such that the product of its decimal digits equals \(N\). In other words, if \(M\) is represented as \(d_1d_2\ldots d_k\), then

[ d_1 \times d_2 \times \cdots \times d_k = N ]

If such an integer \(M\) does not exist, output \(-1\).

Examples:

• If \(N = 10\), the answer is 25, since \(2 \times 5 = 10\).
• If \(N = 17\), the answer is -1 because no combination of digits multiplies to \(17\).
• If \(N = 1\), the answer is 1.

Note: When constructing \(M\), consider that a single digit number (less than 10) always represents itself. For composite numbers, factorize \(N\) using digits from 2 through 9 in a descending manner and then sort the factors in ascending order to form the smallest possible integer.

inputFormat

The input consists of a single integer \(N\) read from standard input.

Constraints:

• \(1 \leq N \leq 10^9\)

outputFormat

Output the smallest positive integer \(M\) whose digits multiply to \(N\), or \(-1\) if no such \(M\) exists. The result should be printed to standard output.

## sample

10

25