Year of More Code Jam (Small)

A new year brings a new calendar and new challenges. Some things do not change. Plenty of good programming contests are still scheduled, and Sphinny still loves them.

Sphinny follows several tournaments. Each tournament consists of a number of rounds. The organizer of a tournament has not fixed the start date yet, but has already fixed how many rounds there are and how many days after the start date each round falls on.

Rounds from different tournaments can land on the same day. Sphinny is happier when more rounds land on one day. For every day that holds $S$ rounds, her happiness grows by $S^2$. Her happiness starts at 0.

The picture below shows three tournaments, one color each, and Sphinny's total happiness is 20. One tournament starts on day 2 of the year, one starts on day 5, and one starts on day 6.

The year has $N$ days. Each tournament starts on one of those $N$ days, and every starting day is equally likely. Compute the expected value of Sphinny's happiness.

Sphinny wants the exact value, not an approximation. There are $T$ tournaments, so there are $N^T$ equally likely ways to choose the start dates. Write the expected happiness as $K + A/B$, where $K$ and $B$ are positive integers and $A$ is a non-negative integer smaller than $B$. If $A$ is 0 then $B$ must be 1, and otherwise the greatest common divisor of $A$ and $B$ must be 1.

A tournament that starts late enough pushes some of its rounds into the next year. Those rounds add nothing to Sphinny's happiness this year.

The first line holds one integer $C$, the number of test cases. The first line of each test case is

N T

where $N$ is the number of days in the year and $T$ is the number of tournaments. $T$ lines follow, one per tournament, in the format

m d2 d3 ... dm

The tournament has $m$ rounds, and its $i$-th round is held on day $d_i$ of the tournament. The first round is always held on day 1, so $d_1 = 1$ is not part of the input and exactly $m - 1$ numbers follow $m$.

Limits

• $1 \le C \le 50$
• $1 \le N \le 10^9$
• $1 \le T \le 3$
• $2 \le m \le 50$
• $1 < d_2 < d_3 < \cdots < d_m \le 10000$

For each test case, print one line in the format

Case #X: K+A/B

where $X$ is the test case number starting from 1, and $K$, $A$ and $B$ are the values described above.