LUCKYNUM  Lucky Numbers
English  Vietnamese 
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:
20170825 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:
20170327 19:12:13
make sure to follow the patten 88666.....6 that cost me 3 WA 

narutorocks:
20160616 17:56:21
NICE BFS 

connektivion:
20160524 16:11:42
same solution with a liitle modification for http://www.spoj.com/problems/ONEZERO works :) 

lotus_guy:
20160111 15:33:07


lotus_guy:
20160111 15:33:06
just preprocess till 100 digits :D


Rahul Lingala:
20141216 18:37:56
Please provide some tricky test cases. Getting WA. 

Bharath Reddy:
20140404 17:07:09
Before solving this, you can try a simpler problem: "ONEZERO". 

yousef hadder:
20140329 20:53:41
Any strong test cases plz :/


nssuresh:
20140119 13:40:00
Beware that input contains spaces and the code should handle it Last edit: 20140119 13:40:56 
Added by:  Duc 
Date:  20090104 
Time limit:  0.490s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  ACM Regional, Ho Chi Minh City 2008 