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
Sigma Kappa: 2017-08-25 21:02:53

Hm, I am getting TLE with a pretty straightforward BFS on a graph with 2*X states. Any tricks needed? I am using scanf, so spaces/newlines in input should not be a problem.

vengatesh15: 2017-03-27 19:12:13

make sure to follow the patten 88666.....6 that cost me 3 WA

narutorocks: 2016-06-16 17:56:21

NICE BFS

connektivion: 2016-05-24 16:11:42

same solution with a liitle modification for http://www.spoj.com/problems/ONEZERO works :)

lotus_guy: 2016-01-11 15:33:07


Last edit: 2016-01-11 15:33:28
lotus_guy: 2016-01-11 15:33:06

just preprocess till 100 digits :D

Rahul Lingala: 2014-12-16 18:37:56

Please provide some tricky test cases. Getting WA.

Bharath Reddy: 2014-04-04 17:07:09

Before solving this, you can try a simpler problem: "ONEZERO".

yousef hadder: 2014-03-29 20:53:41

Any strong test cases plz :/
Edit:
AC, but be careful, the problem was in the input file, it has some extra spaces or newlines.
Nice problem any way :D

Last edit: 2014-03-29 21:49:33
nssuresh: 2014-01-19 13:40:00

Beware that input contains spaces and the code should handle it

Last edit: 2014-01-19 13:40:56

Added by:Duc
Date:2009-01-04
Time limit:0.490s
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