Number Sets

Bạn bắt đầu với một dãy các số nguyên liên tiếp. Bạn muốn nhóm chúng vào các tập hợp.

Bạn được cho một khoảng và một số nguyên \(P\). Ban đầu, mỗi số trong khoảng nằm trong tập hợp riêng của nó.

Sau đó, bạn xem xét từng cặp số nguyên trong khoảng. Nếu hai số nguyên đó chia sẻ một ước nguyên tố chung ít nhất là \(P\), thì bạn hợp nhất hai tập hợp chứa hai số nguyên đó lại với nhau.

Hỏi sẽ có bao nhiêu tập hợp khác nhau sau khi kết thúc quá trình này?

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên \(C\), là số lượng bộ dữ liệu.
Mỗi bộ dữ liệu nằm trên một dòng chứa ba số nguyên cách nhau bởi khoảng trắng \(A\), \(B\), và \(P\). \(A\) và \(B\) là số nguyên đầu tiên và cuối cùng trong khoảng, và \(P\) là số được mô tả ở trên.

Dữ liệu ra

Với mỗi bộ dữ liệu, xuất một dòng chứa chuỗi "Case #X: Y" trong đó X là số thứ tự của bộ dữ liệu (bắt đầu từ 1) và Y là số lượng tập hợp.

Ràng buộc

Phân nhóm

• Tập dữ liệu nhỏ (Test set 1 - Visible): \(1 \le C \le 10\); \(1 \le A \le B \le 1000\); \(2 \le P \le B\).
• Tập dữ liệu lớn (Test set 2 - Hidden): \(1 \le C \le 100\); \(1 \le A \le B \le 10^{12}\); \(B \le A + 1000000\); \(2 \le P \le B\).

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

2
10 20 5
10 20 3

Case #1: 9
Case #2: 7

Nguồn

Google Code Jam 2008, Vòng 1B, bài Number Sets.

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