Description

新的一年带来了新的日历、新的挑战，以及生活中更多的乐趣。然而，有些事情永远不会改变。精彩的编程比赛依旧层出不穷，而我们的主角 Sphinny 对这些比赛的热情始终如一。

Sphinny 对若干项锦标赛感兴趣。每项锦标赛都包含若干轮。每项锦标赛的主办方尚未确定比赛的开始日期，但已经决定了该锦标赛将包含多少轮，以及每一轮距离比赛开始日的天数。

在某些情况下，不同锦标赛的若干轮可能会安排在同一天举行。由于 Sphinny 非常热爱解题，如果同一天有更多的轮次举行，她会更加开心。她的幸福值计算方式如下：对于每一天，若当天有 $S$ 轮比赛，则她的幸福值增加 $S^2$。她的初始幸福值为 $0$（别担心——$0$ 也是个很幸福的起点）。

下图展示了三项锦标赛，每种颜色代表一项锦标赛，Sphinny 的总幸福值为 $20$。有一项锦标赛在当年的第 $2$ 天开始，一项在第 $5$ 天开始，一项在第 $6$ 天开始。

一年共有 $N$ 天。每项锦标赛都可以等概率地在这 $N$ 天中的任意一天开始。今年的大问题是：Sphinny 的期望幸福值是多少？

作为一个完美主义者，她不会只求近似解，而是想要精确的答案。锦标赛的数量为 $T$，因此一共有 $N^T$ 种等可能的锦标赛开始日期的组合。她希望将期望幸福值写成 $K+A/B$ 的形式，其中 $K$ 和 $B$ 为正整数，$A$ 为非负整数且 $A < B$。如果 $A$ 为零，则 $B$ 必须为 $1$；否则 $A$ 和 $B$ 不能有大于 $1$ 的公因数。

如果某项锦标赛开始得太晚，导致其某些轮次安排在下一年，则这些轮次不会对 Sphinny 当年的幸福值产生任何贡献。

Input Format

输入的第一行为一个整数 $C$，表示测试用例数量。接下来有 $C$ 组测试数据。每组测试数据的第一行为

$N\ T$

其中 $N$ 表示一年中的天数，$T$ 表示锦标赛数量。接下来有 $T$ 行，每行描述一项锦标赛，格式如下：

$m\ d_2\ d_3\ \ldots\ d_m$

表示该锦标赛共有 $m$ 轮，第 $i$ 轮将在该锦标赛开始后的第 $d_i$ 天举行。每项锦标赛的第一轮总是在第 $1$ 天举行（即 $d_1=1$）。

Output Format

对于每组测试数据，输出一行，格式如下：

Case #$X$: $K+A/B$

其中 $X$ 为测试编号（从 $1$ 开始），$K$、$A$、$B$ 的含义如上所述。

2
1 1
2 2
4 2
3 2 4
2 3

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

Hint

限制条件

• $1 \leq C \leq 50$
• $1 \leq N \leq 10^{9}$
• $2 \leq m \leq 50$
• $1 < d_2 < d_3 < \ldots < d_m \leq 10000$

小数据集（5 分）

• $1 \leq T \leq 2$

大数据集（12 分）

• $1 \leq T \leq 50$

翻译由 ChatGPT-4.1 完成。