Tatiana thích giữ mọi thứ thật ngăn nắp. Đồ chơi của cô được xếp từ nhỏ đến lớn, bút chì từ ngắn đến dài, còn máy tính từ cũ đến mới. Một ngày nọ, khi luyện đếm, cô nhận thấy một số số nguyên khi được viết ở hệ cơ số 10 và không có chữ số 0 ở đầu thì các chữ số của chúng được sắp theo thứ tự không giảm. Chẳng hạn, 8, 123, 555 và 224488 đều có tính chất này. Cô gọi những số như vậy là số gọn gàng (tidy number). Những số không có tính chất ấy, như 20, 321, 495 và 999990, không phải số gọn gàng.

Cô vừa đếm xong tất cả các số nguyên dương theo thứ tự tăng dần từ 1 đến \(N\). Số gọn gàng cuối cùng mà cô đã đếm là số nào?

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\). Tiếp theo là \(T\) dòng; mỗi dòng mô tả một bộ test bằng một số nguyên \(N\), số cuối cùng Tatiana đã đếm.

Dữ liệu ra

Với mỗi bộ test, in một dòng có dạng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số gọn gàng cuối cùng Tatiana đã đếm.

Ràng buộc

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

Phân nhóm

• Test Set 1 (Visible): \(1 \le N \le 1000\).
• Test Set 2 (Hidden): \(1 \le N \le 10^{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
132
1000
7
111111111111111110

Case #1: 129
Case #2: 999
Case #3: 7
Case #4: 99999999999999999

Nguồn

Google Code Jam 2017, Vòng loại, bài Tidy Numbers.

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