UVA-993 - Product of Digits

• UVa Online Judge 解題結果請於 Submit 後，參閱 uHunt。
• 如果你有任何建議與指教，歡迎於下方留言一起討論喔！
• 本題選為「20170328 大學程式能力檢定 CPE」題目。
• 相同題目：ZOJ-d418

題意概要

給你一個大於等於 $0$ 的整數 $N$，請你你找到最小的自然數 $Q$ ，使得在 $Q$ 中所有數字（digit）的乘積等於 $N$。

• 分析：本題為簡單的貪婪法 (Greedy Method)，如果 $N = 1$，則可以直接回傳 $1$ 即是答案，其他數字 ($N > 1$) 從 $9$ 開始遞減，只要可以整除 $N$ ，就加進答案內。

Input

The first line of input contains one positive integer number, which is the number of data sets. Each subsequent line contains one data set which consists of one non-negative integer number $N$ ($0 \le N \le 109$).

Output

For each data set, write one line containing the corresponding natural number $Q$ or -1 if $Q$ does not exist.

Sample Input

3
1
10
123456789

Sample Output

1
25
-1