Lucky Numbers

View as PDF

Submit solution


Points: 0.14 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
ACM Regional, Ho Chi Minh City 2008
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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.

Output

  • Với mỗi bộ dữ liệu, ghi ra trên một dòng 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

Sample Output

6
8
86
-1

Comments

Please read the guidelines before commenting.


There are no comments at the moment.