LUCKYNUM - Lucky Numbers

no tags 

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

hide comments
lokesh_2052: 2021-07-14 12:11:43

if x%5 == 0 only that case result will be -1


Added by:Jimmy
Date:2009-01-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ACM Regional, Ho Chi Minh City 2008