더 많은 Code Jam의 해

새해가 되면 새 달력과 새로운 도전, 그리고 삶의 수많은 새로운 즐거움이 찾아온다. 하지만 어떤 것들은 결코 변하지 않는다. 여전히 훌륭한 프로그래밍 대회가 많이 열릴 예정이며, 우리의 주인공 Sphinny가 대회에 품은 열정도 변함이 없다.

Sphinny가 관심을 두는 대회가 여러 개 있다. 각 대회는 여러 라운드로 구성된다. 각 대회의 주최자는 대회를 어느 날짜에 시작할지는 정하지 않았지만, 대회에 몇 개의 라운드가 있는지와 각 라운드가 시작일로부터 며칠 뒤에 열리는지는 정했다.

어떤 상황에서는 서로 다른 대회의 라운드가 둘 이상 같은 날에 열리도록 일정이 잡힐 수 있다. Sphinny는 문제 풀이를 무척 좋아하므로, 같은 날에 더 많은 라운드가 열릴수록 더 행복해진다. 행복도는 다음과 같이 계산한다. S개의 라운드가 열리는 각 날짜마다 행복도가 $S^{2}$만큼 증가한다. 행복도는 0에서 시작한다(걱정하지 않아도 된다. 0은 행복하게 시작할 수 있는 값이다).

아래 그림에는 각각 서로 다른 색으로 표시된 세 개의 대회가 있으며, Sphinny의 총 행복도는 20이다. 한 대회는 그해의 둘째 날에 시작하고, 하나는 다섯째 날에 시작하며, 하나는 여섯째 날에 시작한다.

한 해에는 N일이 있다. 각 대회는 N일 중 어느 날에든 동일한 확률로 시작한다. 올해의 중요한 질문은 Sphinny의 행복도의 기댓값이 얼마인가이다.

완벽주의자인 그녀는 이 문제를 근사적으로 풀 생각이 없다. 대신 결과를 정확히 알고 싶어 한다. 대회의 수는 T이고, 대회들의 시작일을 선택하는 동일한 확률의 방법은 $N^{T}$가지이다. 그녀는 행복도의 기댓값을 K+A/B의 형태로 나타내려 한다. 여기서 K와 B는 양의 정수이고, A는 B보다 작은 음이 아닌 정수이다. A가 영이면 B는 반드시 하나여야 하며, 그렇지 않으면 A와 B에는 하나보다 큰 공약수가 없어야 한다.

대회가 그해의 충분히 늦은 시점에 시작하면 일부 라운드는 다음 해에 열리도록 일정이 잡힐 수 있다. 그러한 라운드는 올해 Sphinny의 행복도에 기여하지 않는다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1 GB. 1 ≤ C ≤ 50 1 ≤ N ≤ $10^{9}$ 2 ≤ m ≤ 50 1 < $d_{2}$ < $d_{3}$ < ... < $d_{m}$ ≤ 10000

작은 데이터 세트

1 ≤ T ≤ 2

큰 데이터 세트

1 ≤ T ≤ 50

입력의 첫째 줄에는 테스트 케이스의 수인 정수 C 하나가 주어진다. 이어서 C개의 테스트가 주어진다. 각 테스트 케이스의 첫째 줄은 다음 형식이다.

N T

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

m d_{2} d_{3} ... d_{m}

이는 라운드가 m개 있고, i번째 라운드가 대회의 $d_{i}$일째에 열린다는 뜻이다. 대회의 첫 라운드는 1일째에 열린다($d_{1}$ = 1).

각 테스트마다 다음 형식의 한 줄을 출력한다.

Case #X: K+A/B

여기서 X는 1부터 시작하는 케이스 번호이고, K, A, B는 위에서 설명한 값이다.