#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 ≤ 10^9).

Output

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

LOCAL platform clarification

For this platform, the candidate Q is a nonnegative integer and may be 0. Accordingly N=0 has answer0, and N=1 has answer1. No leading zeroes are used.

3
1
10
123456789

1
25
-1