코드 잼이 많아지는 해 (스몰)

새해가 되면 달력이 바뀌고 새로운 대회가 열린다. 그래도 변하지 않는 것이 있다. 좋은 프로그래밍 대회는 올해도 많이 열리고, 스피니가 대회를 좋아하는 마음도 그대로다.

스피니가 눈여겨보는 대회가 여럿 있다. 각 대회는 여러 라운드로 이루어진다. 주최 측은 대회 시작 날짜를 아직 정하지 않았지만, 라운드가 몇 개인지와 각 라운드가 시작일로부터 며칠째에 열리는지는 이미 정해 두었다.

서로 다른 대회의 라운드가 같은 날에 겹칠 수 있다. 스피니는 하루에 라운드가 많이 열릴수록 더 기뻐한다. 라운드가 $S$개 열리는 날마다 행복도가 $S^2$만큼 늘어난다. 행복도는 0에서 시작한다.

아래 그림은 대회 세 개를 색으로 구분해 보여 준다. 이때 스피니의 행복도는 모두 합쳐 20이다. 한 대회는 그 해의 2일째에, 다른 하나는 5일째에, 나머지 하나는 6일째에 시작한다.

한 해는 $N$일이다. 각 대회는 이 $N$일 중 하루에 시작하고, 어느 날에 시작하든 확률은 모두 같다. 스피니의 행복도의 기댓값을 구하라.

스피니는 근삿값이 아니라 정확한 값을 원한다. 대회가 $T$개이므로 시작 날짜를 고르는 방법은 $N^T$가지이고, 모두 확률이 같다. 기댓값을 $K + A/B$ 꼴로 나타내라. $K$와 $B$는 양의 정수, $A$는 $B$보다 작은 음이 아닌 정수다. $A$가 0이면 $B$는 1이어야 하고, 그렇지 않으면 $A$와 $B$의 최대공약수가 1이어야 한다.

대회가 충분히 늦게 시작하면 일부 라운드는 다음 해로 넘어간다. 넘어간 라운드는 올해의 행복도에 더해지지 않는다.

첫째 줄에 테스트 케이스의 개수 $C$가 주어진다. 각 테스트 케이스의 첫 줄은 다음과 같다.

N T

$N$은 한 해의 날짜 수, $T$는 대회의 개수다. 이어서 대회마다 한 줄씩 $T$개의 줄이 다음 형식으로 주어진다.

m d2 d3 ... dm

이 대회는 라운드가 $m$개이고, $i$번째 라운드는 대회 시작일로부터 $d_i$일째에 열린다. 첫 라운드는 항상 1일째에 열리므로 $d_1 = 1$은 입력에 넣지 않는다. 따라서 $m$ 뒤에는 수가 $m - 1$개 온다.

제한

• $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$

각 테스트 케이스마다 다음 형식으로 한 줄씩 출력한다.

Case #X: K+A/B

$X$는 1부터 시작하는 테스트 케이스 번호이고, $K$와 $A$와 $B$는 문제에서 설명한 값이다.