Bạn đã trở nên nghiện trò chơi thẻ bài mới nhất mang tên PokeCraft: The Gathering. Bạn đã nắm vững luật chơi! Bạn đã xây dựng được các bộ bài cân bằng, tấn công và phòng thủ! Bạn tranh luận về giá trị của các lá bài khác nhau trên các diễn đàn Internet! Bạn thi đấu trong các giải đấu! Và bây giờ, khi họ vừa công bố bộ thẻ bài mới khổng lồ sắp ra mắt vào năm 2010, bạn đã quyết định rằng mình muốn thu thập mọi lá bài cuối cùng trong số đó! May mắn thay, phần lý trí còn sót lại trong não bạn đang tự hỏi: việc này sẽ tốn bao nhiêu chi phí?

Có \(C\) loại thẻ bài trong bộ sắp tới. Các thẻ bài sẽ được bán trong các "gói bổ trợ" (booster packs), mỗi gói chứa \(N\) thẻ bài thuộc các loại khác nhau. Có nhiều tổ hợp có thể có cho một gói bổ trợ mà không có thẻ bài nào bị lặp lại trong cùng một gói. Khi bạn trả tiền cho một gói, bạn sẽ nhận được bất kỳ tổ hợp nào có thể với xác suất như nhau. Bạn mua từng gói một, cho đến khi bạn sở hữu tất cả \(C\) loại thẻ. Số lượng gói bổ trợ dự kiến (trung bình) bạn cần mua là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ thử nghiệm, \(T\). \(T\) bộ thử nghiệm tiếp theo, mỗi bộ gồm một dòng chứa \(C\) và \(N\).

Dữ liệu ra

Đối với mỗi bộ thử nghiệm, hãy xuất một dòng theo định dạng:

Case #x: E

trong đó \(x\) là số thứ tự bộ thử nghiệm, bắt đầu từ 1, và \(E\) là số lượng gói bổ trợ dự kiến bạn cần mua. Bất kỳ câu trả lời nào có sai số tương đối hoặc tuyệt đối không quá \(10^{-5}\) đều sẽ được chấp nhận.

Ràng buộc

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

Phân nhóm

• Small dataset: \(1 \le N \le C \le 10\)
• Large dataset: \(1 \le N \le C \le 40\)

Đ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
2 1
3 2

Case #1: 3.0000000
Case #2: 2.5000000

Nguồn

Google Code Jam 2009, Vòng 1A, bài Collecting Cards.

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