자전거 그림 퍼즐

Per와 Gunnar가 자전거 그림 맞추기 게임을 하나 찾았다. 둘 다 승부욕이 강해서 누가 더 잘하는지 가리기로 했다. 게임의 목표는 뒤섞인 자전거 그림을 원래대로 되돌리는 것이다.

한 판이 시작되면 자전거 그림을 가로 $W$개, 세로 $H$개의 똑같은 크기 직사각형으로 자른 뒤 무작위로 섞는다. 섞인 그림은 모두 같은 확률로 나온다. 플레이어는 직사각형 두 개를 마음대로 골라 자리를 맞바꿀 수 있고, 그림이 완성될 때까지 이 동작을 반복한다. 게임은 자리를 맞바꾼 횟수를 세며, 그 횟수가 그 판의 점수다.

Gunnar는 한 판을 끝낸 뒤 자기 점수를 $W$, $H$와 함께 Per에게 보내고 이겨 보라고 했다. Per는 조각이 운 나쁘게 섞이면 Gunnar의 점수를 이기는 것이 아예 불가능하다는 사실을 곧 알아차렸다. 점수는 낮을수록 좋으므로, Per가 이기려면 맞바꾼 횟수가 Gunnar의 점수보다 적어야 한다.

Per가 언제나 최선으로 플레이한다고 할 때, Gunnar의 점수를 이길 확률을 구하라.

첫 줄에 시나리오의 개수 $T$가 주어진다. 이어지는 $T$개의 줄에는 각각 세 정수 $W$, $H$, $S$가 주어진다. $S$는 Gunnar가 마지막으로 낸 점수다.

• $0 < T \le 150$
• $0 < W \le 5$
• $0 < H \le 4$
• $0 \le S \le W \times H$
• 두 점수를 비교할 때는 더 작은 쪽이 더 좋다.

각 시나리오마다 Per가 Gunnar의 점수를 이길 확률을 한 줄에 출력한다. 확률은 기약분수로 나타내고 분자와 분모를 /로 구분한다. 답이 정수이면 분자만 출력한다.