In some Asian countries, 8 and 6 are considered lucky digits. Any number containing only 8s and 6s is considered lucky number, e.g. 6, 8, 66, 668, 88, 886 …. Nguyen is a student who likes mathematics very much. Nguyen likes lucky numbers but only of the form

S = 8…86…6

where S has at least one digit and the number of 8s or 6s can be zero. Examples of S are 8, 88, 6, 66, 86, 886, 8866 …

Given a positive integer X (1 < X < 10 000), Nguyen wants to find the smallest lucky number S which has at most 200 digits and is divisible by X.

Your task is to write a program to find that number for Nguyen.

Input

The input file consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 20. The following lines describe the data sets.

For each data test, there is one single line containing the integer X.

Output

For each data test, write in one line the smallest lucky number S which is divisible by X. In case there is no such a number which has at most 200 digits, write -1.

Example

Sample Input
4
6
8
43
5	

Sample Output
6
8
86
-1