Năm \(2021\) đang xảy ra một điều đã hơn một thế kỷ không xuất hiện. Giống năm \(1920\) trước đó, \(2021\) là một năm gầm vang (roaring year).

Một năm biểu diễn bởi số nguyên dương \(y\) là gầm vang nếu cách viết thập phân không có số \(0\) ở đầu của \(y\) là phép nối cách viết thập phân không có số \(0\) ở đầu của ít nhất hai số nguyên dương phân biệt, liên tiếp, theo thứ tự tăng. Vì \(2021\) là phép nối của \(20\) và \(21\), nó là năm gầm vang.

Các ví dụ khác là \(12\), \(789\), \(910\), \(1234\) và \(9899100\). Năm \(2020\) không gầm vang vì danh sách duy nhất gồm ít nhất hai số dương nối thành \(2020\) là \([20,20]\), không phải các số liên tiếp.

Tương tự, \(2019\) chỉ có ba cách tách: \([20,1,9]\), \([201,9]\) và \([20,19]\). Hai danh sách đầu không gồm các số liên tiếp; danh sách cuối không tăng. Do đó \(2019\) cũng không gầm vang. Cuối cùng, \(778\) không gầm vang vì \([7,78]\) và \([77,8]\) không gồm các số liên tiếp, còn \([7,7,8]\) không gồm các số phân biệt.

Cho năm hiện tại — có thể gầm vang hoặc không — hãy tìm năm gầm vang kế tiếp.

Dữ liệu vào

Dòng đầu chứa số bộ dữ liệu \(T\). Mỗi dòng tiếp theo chứa một số nguyên \(Y\), là năm hiện tại.

Dữ liệu ra

Với mỗi bộ dữ liệu, in Case #x: z, trong đó \(x\) là số thứ tự (bắt đầu từ \(1\)), còn \(z\) là năm gầm vang đầu tiên lớn hơn nghiêm ngặt \(Y\).

Ràng buộc

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

Phân nhóm

• Test Set 1 (Visible Verdict): \(1\le Y\le10^6\).
• Test Set 2 (Hidden Verdict): \(1\le Y\le10^{18}\).

Đ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ụ

4
2020
2021
68000
101

Case #1: 2021
Case #2: 2122
Case #3: 78910
Case #4: 123

Nguồn

Google Code Jam 2021, Vòng 1C, bài Roaring Years.

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