For a given positive integer number N, write a complete program to find the minimal natural M such that the product of digits of M is equal N. N is less than 1,000,000,000. If no M exists, print -1. Your code should not take more than 10 secs for any case.
Sample Inputs
1
3
15
10
123456789
32
432
1296
Sample Outputs
1
3
35
25
-1
48
689
2899
Please help with the code!
Thank you in advance.