#993Product of Digits

For a given non-negative integer number N , find the minimal natural Q such that the product of all digits of Q is equal 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 ≤ N ≤ 109).

Output

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

3
1
10
123456789

1
25
-1