Given an integer N (0 <= N < 10⁷), find the smallest positive integer M (M > 0) such that the product of digits of M equals N.

Input

The first line of input is T (the total number of test cases), followed by T (T < 10001) lines, each containing an integer N.

Output

For each integer N, output in a separate line the integer M, or -1 (if encoding is not possible).

Example

Input:
3
24
5
11
Output:
38
5
-1