Cho tới hôm nay, quốc gia của bạn dùng \(D\) mệnh giá tiền xu nguyên dương khác nhau cho mọi giao dịch. Hôm nay, nữ hoàng nổi giận khi một thần dân nộp thuế bằng một bao tiền xu mệnh giá thấp khổng lồ, và vừa ra sắc lệnh rằng trong một lần mua không được dùng quá \(C\) đồng của bất kỳ một mệnh giá nào.

Chẳng hạn, nếu \(C=2\) và các mệnh giá hiện có là 1 và 5, ta có thể mua món hàng giá trị 11 bằng hai đồng 5 và một đồng 1, hoặc giá trị 12 bằng hai đồng 5 và hai đồng 1, nhưng không thể mua món hàng giá trị 9 hay 17.

Bạn không thể trực tiếp phản đối sắc lệnh, nhưng tình cờ lại phụ trách xưởng đúc tiền và có thể phát hành các mệnh giá mới. Bạn muốn có thể mua mọi món hàng có giá trị nguyên dương không quá \(V\) theo quy định mới. (Điều này không nhất thiết đã khả thi trước sắc lệnh.) Đồng thời, bạn muốn đưa vào ít mệnh giá mới nhất có thể, và tập hợp cuối cùng gồm cả mệnh giá cũ lẫn mới không được có phần tử trùng nhau.

Cần ít nhất bao nhiêu mệnh giá mới?

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test gồm một dòng chứa ba giá trị \(C\), \(D\), \(V\), sau đó là một dòng chứa \(D\) mệnh giá hiện có đôi một khác nhau, cách nhau bởi dấu cách và được sắp tăng dần.

Dữ liệu ra

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

Ràng buộc

• \(1 \le T \le 100\).
• Mỗi mệnh giá hiện có không vượt quá \(V\).

Phân nhóm

• Test Set 1 (Nhỏ): \(C=1\), \(1 \le D \le 5\), \(1 \le V \le 30\).
• Test Set 2 (Lớn): \(1 \le C \le 100\), \(1 \le D \le 100\), \(1 \le V \le 10^9\).

Đ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
1 2 3
1 2
1 3 6
1 2 5
2 1 3
3
1 6 100
1 5 10 25 50 100

    ???+ success "Output"

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

??? "Giải thích"

    Lưu ý Case #3 và #4 không nằm trong giới hạn của bộ Nhỏ.

    Trong Case #1, với tối đa một đồng mỗi mệnh giá hiện có, ta đã tạo được mọi giá trị cần thiết 1, 2 và 3.

    Trong Case #2, chỉ cần thêm mệnh giá 3 hoặc 4; chọn mệnh giá nào cũng chỉ cần đúng một mệnh giá mới.

    Trong Case #3, lời giải tối ưu là thêm mệnh giá 1.

Nguồn

Google Code Jam 2015, Vòng 1C, bài Less Money, More Problems.

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