Cô cừu Bleatrix Trotter nghĩ ra một chiến lược giúp mình ngủ nhanh hơn. Trước tiên, cô chọn một số \(N\). Sau đó cô bắt đầu đọc \(N,2\times N,3\times N,\ldots\). Mỗi lần đọc một số, cô nghĩ đến tất cả chữ số trong số đó. Cô theo dõi những chữ số trong 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 đã từng nhìn thấy ít nhất một lần trong bất kỳ số nào đã đọc. Ngay khi đã thấy đủ cả mười chữ số, cô sẽ ngủ thiếp đi.

Bleatrix phải bắt đầu bằng \(N\) và luôn phải đọc \((i+1)\times N\) ngay sau \(i\times N\). Ví dụ, giả sử cô chọn \(N=1692\), cô sẽ đếm như sau:

• \(N=1692\). Lúc này cô đã thấy các chữ số 1, 2, 6 và 9.
• \(2N=3384\). Lúc này cô đã thấy 1, 2, 3, 4, 6, 8 và 9.
• \(3N=5076\). Lúc này cô đã thấy đủ mười chữ số và ngủ thiếp đi.

Số cuối cùng cô đọc trước khi ngủ là gì? Nếu cô sẽ đếm mãi mãi, hãy in INSOMNIA.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test gồm một dòng chứa số nguyên \(N\) mà Bleatrix đã chọn.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y là số cuối cùng Bleatrix đọc trước khi ngủ theo các quy tắc trên.

Ràng buộc

• \(1\le T\le100\).

Phân nhóm

• Test Set 1 (Hiển thị): \(0\le N\le200\).
• Test Set 2 (Ẩn): \(0\le N\le10^6\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

5
0
1
2
11
1692

Case #1: INSOMNIA
Case #2: 10
Case #3: 90
Case #4: 110
Case #5: 5076

Nguồn

Google Code Jam 2016, Vòng loại, bài Counting Sheep.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.