Product 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$\le$N$\le$10⁹) .

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