問題文

集合 {ab | 1aN, 1bM, abは互いに素な整数}\left\{\frac{a}{b}\ \middle|\ 1 \le a \le N,\ 1 \le b \le M,\ aとbは互いに素な整数 \right\} のうち、小さい方から KK 番目の要素を求めよ。

制約

  • 入力はすべて整数である。
  • 一つの入力ファイルに TT 個のテストケースを含む。以下、 N,M,KN, M, K にテストケースの番号 1,...,T1, ..., T をつける。
  • 1T1,0001 \le T \le 1,000
  • 1Ni15,0001 \le N_i \le 15,000
  • 1Mi15,0001 \le M_i \le 15,000
  • 1KiNiMi1 \le K_i \le N_i M_i
  • i=1TNi15,000\sum_{i=1}^T N_i \le 15,000
  • i=1TMi15,000\sum_{i=1}^T M_i \le 15,000

入力

TT
N1 M1 K1N_1\ M_1\ K_1
\vdots
NT MT KTN_T\ M_T\ K_T

出力

各テストケースに対して出力し、テストケースごとに改行せよ。
各テストケースの答えは以下のように出力せよ。

  • 答えが整数である場合、そのまま
  • 答えが整数でない場合、分子/分母の形式
  • 答えが存在しない場合、-1

サンプル

入力1
8
2 4 1
2 4 2
2 4 3
2 4 4
2 4 5
2 4 6
2 4 7
2 4 8
出力1
1/4
1/3
1/2
2/3
1
2
-1
-1

N=2, M=4N = 2,\ M = 4 のとき、集合は {14, 13, 12, 23, 1, 2}\{ \frac{1}{4},\ \frac{1}{3},\ \frac{1}{2},\ \frac{2}{3},\ 1,\ 2 \} となる。

提出


Go (1.21)