問題文
集合 {ba 1≤a≤N, 1≤b≤M, aとbは互いに素な整数} のうち、小さい方から K 番目の要素を求めよ。
制約
- 入力はすべて整数である。
- 一つの入力ファイルに T 個のテストケースを含む。以下、 N,M,K にテストケースの番号 1,...,T をつける。
- 1≤T≤1,000
- 1≤Ni≤15,000
- 1≤Mi≤15,000
- 1≤Ki≤NiMi
- ∑i=1TNi≤15,000
- ∑i=1TMi≤15,000
入力
出力
各テストケースに対して出力し、テストケースごとに改行せよ。
各テストケースの答えは以下のように出力せよ。
- 答えが整数である場合、そのまま
- 答えが整数でない場合、
分子/分母
の形式
- 答えが存在しない場合、
-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=4 のとき、集合は {41, 31, 21, 32, 1, 2} となる。