Smallest Product Digit Combination

You are given a positive integer \(n\). Your task is to find the smallest positive integer \(x\) such that the product of the digits of \(x\) is exactly \(n\). If there is no such positive integer, output -1.

For example, when \(n=18\), one possibility is \(x=29\) since \(2 \times 9 = 18\). Given multiple possibilities, choose the smallest \(x\) in numerical order. Use the fact that any factorization of \(n\) into digits from 2 to 9 can lead to a candidate solution by sorting the digits in increasing order.

Note: The number 1 is considered as a valid answer only when \(n=1\).

inputFormat

The input consists of a single integer \(n\) (\(1 \le n \le 10^{9}\)), given via standard input.

outputFormat

Output a single integer, which is the smallest positive integer \(x\) such that the product of its digits equals \(n\). If no such integer exists, output -1.

18

29