A Year of More Contests

A new year brings a new calendar and a fresh run of programming contests. Sphinny plans her year around them again.

Sphinny follows several tournaments. Each tournament has a fixed number of rounds, and the organizer has already fixed how many days after the tournament start each round takes place. The start date itself is still undecided.

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

The picture below shows three tournaments in three colors. One starts on day 2 of the year, one on day 5, and one on day 6, and Sphinny's happiness adds up to 20.

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

Sphinny does not want an approximation. There are $T$ tournaments and $N^T$ equally likely ways to pick 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 pushes some of its rounds into the next year. Rounds that fall into the next year do not add to this year's happiness.

The first line holds the number of test cases $C$. The first line of each test case has the form

N T

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

m d2 d3 ... dm

This tournament has $m$ rounds, and its $i$-th round is held on day $d_i$ counted from the start of that tournament. The first round is always on day 1, so $d_1 = 1$ is not printed.

Limits

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

For each test case print one line of the form

Case #X: K+A/B

where $X$ is the case number starting from 1, and $K$, $A$, $B$ are as described in the statement.