Ta có một danh sách các số nguyên \(X_1,X_2,\ldots,X_N\). Ta muốn chúng theo thứ tự tăng nghiêm ngặt, nhưng không được phép đổi thứ tự các phần tử, nên các thuật toán sắp xếp thông thường không dùng được.

Lựa chọn duy nhất là thay đổi các số bằng cách nối các chữ số từ \(0\) đến \(9\) vào bên phải biểu diễn thập phân của chúng. Chẳng hạn, từ số \(10\), một thao tác có thể biến nó thành \(10\mathbf0\) hoặc \(10\mathbf9\); hai thao tác có thể biến nó thành \(10\mathbf{34}\), như hình dưới.

Cho danh sách hiện tại, cần ít nhất bao nhiêu thao tác nối một chữ số để danh sách trở thành tăng nghiêm ngặt? Ví dụ, với danh sách \(100,7,10\), ta có thể dùng tổng cộng \(4\) thao tác để tạo một danh sách đã sắp xếp như hình:

Dữ liệu vào

Dòng đầu chứa số bộ dữ liệu \(T\). Mỗi bộ được mô tả trên hai dòng. Dòng đầu chứa một số nguyên \(N\), là số phần tử của danh sách. Dòng thứ hai chứa \(N\) số nguyên \(X_1,X_2,\ldots,X_N\), là các phần tử theo đúng thứ tự đã cho.

Dữ liệu ra

Với mỗi bộ dữ liệu, in Case #x: y, trong đó \(x\) là số thứ tự bộ dữ liệu (bắt đầu từ \(1\)), còn \(y\) là số thao tác nối một chữ số ít nhất cần dùng để danh sách tăng nghiêm ngặt.

Ràng buộc

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

Phân nhóm

• Test Set 1 (Visible Verdict): \(2\le N\le3\); \(1\le X_i\le100\) với mọi \(i\).
• Test Set 2 (Visible Verdict): \(2\le N\le100\); \(1\le X_i\le10^9\) với mọi \(i\).

Đ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
3
100 7 10
2
10 10
3
4 19 1
3
1 2 3

Case #1: 4
Case #2: 1
Case #3: 2
Case #4: 0

Nguồn

Google Code Jam 2021, Vòng 1A, bài Append Sort.

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