Smallest Integer with Given Digit Product

Given a positive integer \( n \), your task is to find the smallest positive integer \( x \) such that the product of its digits equals \( n \). The product of the digits of an integer is computed by multiplying all individual digits (e.g., for \( x=49 \), the product is \( 4 \times 9 = 36 \)). If no such integer exists, output \( -1 \).

Example:

• If \( n=36 \), one valid \( x \) is 49 since \( 4 \times 9 = 36 \) and there is no smaller number satisfying this condition.
• If \( n=17 \), output \( -1 \) because no combination of digits produces a product of 17.

This problem requires you to factorize \( n \) using digits between \( 2 \) and \( 9 \), and then to combine these factors in an ascending order to form the smallest possible integer. If \( n=1 \), then the answer is simply \( 1 \).

inputFormat

The input consists of a single integer \( n \) (where \( 1 \le n \le 10^9 \)) provided via standard input (stdin).

outputFormat

Output the smallest positive integer \( x \) whose digits multiply to \( n \). If no such integer exists, output \( -1 \).

36

49