Bạn đang viết một danh sách các số. Danh sách của bạn chứa tất cả các số có đúng \(D_i\) chữ số trong biểu diễn thập phân của nó bằng \(i\), với mỗi \(i\) từ 1 đến 9, bao gồm cả hai đầu. Bạn đang viết chúng theo thứ tự tăng dần.

Ví dụ, bạn có thể đang viết mọi số có hai chữ số '1' và một chữ số '5'. Danh sách của bạn sẽ bắt đầu bằng 115, 151, 511, 1015, 1051.

Cho \(N\), là số cuối cùng bạn đã viết, hãy tính số tiếp theo trong danh sách sẽ là gì.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên \(T\), số lượng bộ dữ liệu kiểm tra. \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(N\).

Dữ liệu ra

Đối với mỗi bộ dữ liệu, hãy xuất:

Case #X: K

Ràng buộc

• \(1 \le T \le 500\) (đối với Large dataset).

Phân nhóm

• Small dataset: \(1 \le N \le 10^6\), \(1 \le T \le 50\).
• Large dataset: \(1 \le N \le 10^{20}\), \(1 \le T \le 500\).

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

3
115
1051
6233

Case #1: 151
Case #2: 1105
Case #3: 6323

Nguồn

Google Code Jam 2009, Vòng 1B, bài The Next Number.

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