Untitled

Lucky number
Trong một số nước châu Á, 8 và 6 được coi là những chữ số may mắn. Bất cứ số nguyên nào chỉ chứa chữ số 8 và 6 được coi là số may mắn, ví dụ 6, 8, 66, 668, 88, 886 …. Nguyên là một học sinh rất thích toán. Nguyên thích các số may mắn nhưng chỉ thích các số có dạng
S = 8…86…6
trong đó S có ít nhất một chữ số và chữ số 6 và 8 không nhất thiết phải đồng thời xuất hiện. Ví dụ, 8, 88, 6, 66, 86, 886, 8866 … là các số có dạng S.
Cho trước một số nguyên dương X (1 < X < 10 000), Nguyên muốn tìm số may mắn nhỏ nhất dạng S, có không quá 200 chữ số và chia hết cho X.
Nhiệm vụ của bạn là viết một chương trình tìm số đó cho Nguyên.
Input
Dữ liệu vào gồm nhiều bộ dữ liệu tương ứng với nhiều test. Dòng đầu tiên chứa một số nguyên dương không lớn hơn 20 là số lượng các bộ dữ liệu. Các dòng tiếp theo chứa các bộ dữ liệu.
Trên mỗi dòng tiếp theo chứa một số nguyên X tương ứng với mỗi bộ dữ liệu.
Ouput
Với mỗi bộ dữ liệu, ghi ra số may mắn dạng S nhỏ nhất chia hết cho X. Trường hợp không tồn tại số S có không quá 200 chữ số như vậy, ghi -1.
Sample
Input	
4
6
8
43
5	
 
Output
Case #1
6
Case #2
8
Case #3
86
Case #4
-1

20
5272
9040
7610
4000
5391
2268
2008
9668
576
134
2162
1792
3518
5198
1968
9774
653
813
8194
2403