Smallest Number with Given Digit Product

Given an integer (N), find the smallest positive integer (S) such that the product of its digits equals (N), i.e., (\prod_{i=1}^{k} d_i = N). If no such number exists, output (-1). The number (S) should be minimal in value when considered as a positive integer.

For example, for (N=10), one valid decomposition is (2 \times 5 = 10), yielding (S=25).

inputFormat

The input is given via standard input (stdin). The first line contains an integer (T) denoting the number of test cases. Each of the following (T) lines contains one integer (N).

outputFormat

For each test case, output on a new line the smallest positive integer (S) whose digits multiply to (N). If no such number exists for a test case, output (-1). The output should be printed to standard output (stdout).## sample

5
1
10
25
7
37

1
25
55
7
-1