Sinh số
Đề bài
Mô tả
Ging đang phát triển thế hệ máy tính tiếp theo: "máy tính Tanquum".
"Máy tính Tanquum" tận dụng những thành tựu vật lý tiên tiến, cho phép sắp xếp lại các chữ số của mọi số nguyên dương chỉ trong một lệnh.
Ứng dụng của nó là vô hạn. Ví dụ, từ số , "máy tính Tanquum" có thể tạo ra mọi số nguyên dương chỉ với hai loại lệnh: tăng một đơn vị và sắp xếp lại.
Cụ thể hơn, chỉ có hai thao tác sau được phép thực hiện trên số nguyên :
- Tăng thêm , tức là gán .
- Sắp xếp lại các chữ số của . Kết quả không được có chữ số ở đầu. Ví dụ, từ , với một lệnh loại này, bạn có thể thu được một trong các số sau: , , , .
Vì "máy tính Tanquum" rất tiên tiến, nó luôn chỉ dùng số lệnh ít nhất.
Bạn vừa được Ging tuyển để hỗ trợ phát triển "máy tính Tanquum". Nhiệm vụ đầu tiên của bạn là kiểm tra tính đúng đắn của "máy tính Tanquum". Cho một số , hãy tìm số lệnh ít nhất cần dùng để biến thành .
Dữ liệu vào
Dòng đầu tiên chứa một số nguyên () là số bộ dữ liệu.
dòng tiếp theo, mỗi dòng chứa một số nguyên ().
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra trên một dòng số lệnh ít nhất.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 5 26 843 |
4 17 44 |
Cần lần tăng để tạo ra số . Có thể tạo ra bằng lệnh: lần tăng để được , lần sắp xếp lại để được , rồi lần tăng để được . |
| 4 1 9 10 100 |
0 8 9 28 |
Ví dụ bổ sung (không có trong đề gốc). Số không cần lệnh nào. Số : tăng ( lệnh), sắp xếp lại thành , rồi tăng lần tới . |
Bình luận