Một năm mới mang đến một bộ lịch mới, những thử thách mới và nhiều niềm vui mới trong cuộc sống. Tuy nhiên, có một số thứ không bao giờ thay đổi. Vẫn còn nhiều cuộc thi lập trình tuyệt vời sắp được tổ chức, và niềm đam mê của nữ anh hùng Sphinny dành cho chúng vẫn không hề giảm bớt.

Có một số giải đấu mà Sphinny quan tâm. Mỗi giải đấu sẽ bao gồm một số vòng thi. Ban tổ chức của mỗi giải đấu chưa quyết định ngày bắt đầu giải đấu, nhưng đã quyết định sẽ có bao nhiêu vòng thi và mỗi vòng thi sẽ diễn ra sau ngày bắt đầu bao nhiêu ngày.

Trong một số tình huống, hai hoặc nhiều vòng thi (từ các giải đấu khác nhau) có thể được lên lịch vào cùng một ngày. Vì Sphinny rất thích giải quyết vấn đề, cô ấy sẽ hạnh phúc hơn nếu có nhiều vòng thi được lên lịch vào cùng một ngày hơn. Giá trị hạnh phúc của cô ấy được tính như sau: đối với mỗi ngày có \(S\) vòng thi, hạnh phúc của cô ấy sẽ tăng thêm \(S^2\). Hạnh phúc của cô ấy bắt đầu từ 0 (đừng lo lắng — 0 là một điểm khởi đầu hạnh phúc).

Trong hình dưới đây có ba giải đấu, mỗi giải được đại diện bởi một màu khác nhau, và tổng hạnh phúc của Sphinny là 20. Một giải đấu bắt đầu vào ngày thứ hai của năm, một giải bắt đầu vào ngày thứ năm của năm, và một giải bắt đầu vào ngày thứ sáu của năm.

Có \(N\) ngày trong năm. Mỗi giải đấu sẽ bắt đầu vào bất kỳ ngày nào trong \(N\) ngày với xác suất như nhau. Câu hỏi lớn cho năm nay là giá trị kỳ vọng của hạnh phúc của Sphinny là bao nhiêu.

Là một người cầu toàn, cô ấy sẽ không giải quyết vấn đề một cách xấp xỉ. Thay vào đó, cô ấy muốn biết kết quả chính xác. Số lượng giải đấu là \(T\), và có \(N^T\) cách chọn ngày bắt đầu của các giải đấu với xác suất như nhau. Cô ấy sẽ biểu diễn hạnh phúc kỳ vọng của mình dưới dạng \(K + A/B\), trong đó \(K\) và \(B\) là các số nguyên dương và \(A\) là một số nguyên không âm nhỏ hơn \(B\). Nếu \(A\) bằng 0 thì \(B\) phải bằng 1, ngược lại \(A\) và \(B\) không được có ước chung lớn hơn 1.

Nếu một giải đấu bắt đầu đủ muộn trong năm, một số vòng thi của nó có thể được lên lịch vào năm sau. Những vòng thi đó không đóng góp vào hạnh phúc của Sphinny trong năm nay.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào là một số nguyên duy nhất \(C\), số lượng bộ test. \(C\) bộ test tiếp theo. Dòng đầu tiên của mỗi bộ test có dạng:

N T

trong đó \(N\) là số ngày trong năm, và \(T\) là số lượng giải đấu. \(T\) dòng sau đó, mỗi dòng cho một giải đấu, theo định dạng:

m d2 d3 ... dm

cho biết có \(m\) vòng thi, và vòng thứ \(i\) sẽ được tổ chức vào ngày thứ \(d_i\) của giải đấu. Vòng đầu tiên của một giải đấu được tổ chức vào ngày 1 (\(d_1 = 1\)).

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng có dạng:

Case #X: K+A/B

trong đó \(X\) là số thứ tự bộ test, bắt đầu từ 1, và \(K, A, B\) như đã mô tả ở trên.

Ràng buộc

• \(1 \le C \le 50\)
• \(1 \le N \le 10^9\)
• \(2 \le m \le 50\)
• \(1 < d_2 < d_3 < \dots < d_m \le 10000\)

Phân nhóm

• Small dataset: \(1 \le T \le 2\)
• Large dataset: \(1 \le T \le 50\)

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

Case #1: 1+0/1
Case #2: 5+1/8

Nguồn

Google Code Jam 2009, Chung kết thế giới, bài Year of More Code Jam.

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