UVa 993

993 - Product of digits

• UVA: [1]
• Timus: [2]

Summary

Given a number N, determine the smallest positive integer whose digits have a product of N. (0<=N<=10^9)

Explanation

For most numbers, you need to break the number down into factors below 10, then print the digits in ascending order. The smallest number tries to have as many large factors as possible (i.e. maximum number of 9s, followed by maximum 8s, etc.), and the result is printed in ascending order.

Gotchas

• The output must be a positive integer for all values of N.

Input

3 
1 
10 
123456789

Output

1 
25 
-1

References

1. Reference 1