고양이에게 과자 나눠 주기

Albert는 고양이 $N$ 마리를 키우고 있는데 편의상 번호가 1부터 $N$까지 붙어있다. 오늘은 간식으로 고양이용 과자 $M$개를 나눠주려고 하는데 각 과자는 1번 부터 $M$번까지 번호가 붙어있고, 모두 동일한 크기이다. $j$ 번째 과자는 균등한 크기의 $V\_j$ 조각으로 쪼개져있고, 이는 $N$ 마리의 고양이들이 적절히 나눠먹는다 - $i$번째 고양이가 먹은 $j$번 과자 조각의 수를 $A\_{j, i}$라 하자. 이 때, $\sum\_{1 \le i \le N} A\_{j, i} = V\_j$ 를 항상 만족한다.

예를 들어 $N = 3$, $M = 3$, $V = \[2, 3, 5]$, $A = \[ \[0, 1, 1], \[1, 2, 0], \[2, 1, 2] ]$ 라 하자.

• 과자는 총 3개이며 순서대로 2조각, 3조각, 5조각으로 나뉘어져있다.
• $A\_{1, \cdot} = \[0, 1, 1]$ 이므로 1번 과자는 2번과 3번 고양이가 각각 한 조각씩 먹었다. 즉, 두 고양이가 과자 반개씩 먹은셈이다.
• $A\_{2, \cdot} = \[1, 2, 0]$ 이므로 2번 과자는 1번 고양이가 한 조각, 2번 고양이가 두 조각 먹었다. 즉, 두 고양이가 각각 과자 (1/3)개와 (2/3)개씩 먹은셈이다.
• $A\_{3, \cdot} = \[2, 1, 2]$ 이므로 3번 과자는 세 마리의 고양이가 각각 (2/5), (1/5), (2/5) 조각씩 먹은 셈이다.
• 1번 고양이는 총 $(1/3) + (2/5) = (11/15)$ 개의 과자를, 2번 고양이는 총 $(1/2) + (2/3) + (1/5) = (41/30)$ 개의 과자를, 3번 고양이는 총 $(1/2) + (2/5) = (9/10)$ 개의 과자를 먹었다.

Albert는 고양이들이 모두 간식을 먹은 후 가장 많이 먹은 고양이와 가장 적게 먹은 고양이가 먹은 양의 차이가 궁금하다. 위 예제에서는 2번 고양이가 가장 많이 먹었고 1번 고양이가 가장 적게 먹었는데, 그 차이는 (19/30)개이다. Albert를 도와주자.

입력 첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 $N$과 $M$이 공백으로 구분되어 주어진다. 다음 $M$줄에 걸쳐 $j$번재 줄은 $j$번째 과자의 조각 수를 나타내는 $V\_j$와 함께 $N$마리의 고양이들이 몇 조각씩 먹었는지 알려주는 $A\_{j, \cdot}$ 배열의 값이 주어진다 -- 즉, 총 $N+1$ 개의 정수가 공백으로 구분되어 주어진다.

각 테스트 케이스의 정답을 기약 분수 형태로 출력한다. 단, 답이 정수인 경우 정수 형태로 출력한다 (예제 참고).

• $1 \le T \le 20$

• $1 \le N, M \le 50$

• $1 \le j \le M$인 $j$에 대하여:

  • $1 \le V\_j \le 20$
  • $V\_j = \sum\_{1 \le i \le N} A\_{j, i}$
  • $1 \le i \le N$ 인 $i$에 대하여 $0 \le A\_{j, i} \le V\_j$

• 입력으로 주어지는 모든 테스트 케이스에 대하여 정답이 정수 $x$ 혹은 기약 분수 $p/q$ 일 때, $x, p, q$는 모두 $10^{11}$ 이하인 정수임이 보장된다.

기약 분수 - 이 문제에서 답이 정수가 아닌 분수일 경우 $p/q$ 꼴인 기약 분수로 출력해야하며, 기약 분수란 $p, q$의 최대 공약수가 1인 경우를 이야기한다. 예제 3의 경우 2/9 가 정답이며 4/18 이나 6/27 등은 기약 분수가 아니므로 정답으로 인정하지 않는다.