Trong cuộc thi biểu diễn thơ đếm số, một người biểu diễn cầm micro, chọn một số \(N\) rồi đếm thành tiếng từ 1 tới \(N\). Cụ thể, cô bắt đầu bằng cách đọc 1, sau đó liên tục đọc số lớn hơn số vừa đọc đúng 1 đơn vị và dừng lại sau khi đọc \(N\).

Đến lượt bạn biểu diễn, nhưng bạn thấy quá trình này nhàm chán và muốn thêm một biến tấu để tăng tốc: đôi khi, thay vì cộng 1 vào số trước đó, bạn có thể đảo thứ tự các chữ số của số đó, đồng thời bỏ mọi số 0 ở đầu được tạo ra. Ví dụ, sau khi đọc 16, số tiếp theo có thể là 17 hoặc 61; sau khi đọc 2300, số tiếp theo có thể là 2301 hoặc 32. Bạn có thể đảo số bao nhiêu lần tùy ý, kể cả không lần nào, trong một màn biểu diễn.

Số đầu tiên bạn đọc phải là 1. Số lượng số ít nhất bạn phải đọc để đạt tới \(N\) là bao nhiêu? Cả 1 và \(N\) đều được tính vào tổng này. Nếu đọc cùng một số nhiều lần, mỗi lần đọc đều được tính riêng.

Dữ liệu vào

Dòng đầu tiên chứa số bộ test \(T\). Mỗi trong \(T\) dòng tiếp theo chứa một số nguyên \(N\), là số bạn phải đạt tới.

Dữ liệu ra

Với mỗi bộ test, in một dòng dạng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1) và \(y\) là số lượng số ít nhất bạn cần đọc.

Ràng buộc

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

Phân nhóm

• Nhỏ: \(1 \le N \le 10^6\).
• Lớn: \(1 \le N \le 10^{14}\).

Đ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
1
19
23

Case #1: 1
Case #2: 19
Case #3: 15

Nguồn

Google Code Jam 2015, Vòng 1B, bài Counter Culture.

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