解説

問題文で述べられた集合を $S$ とします。 $S = \left\{\frac{a}{b}\ \middle|\ 1 \le a \le N,\ 1 \le b \le M,\ aとbは互いに素な整数 \right\}$
また、$x$ を超えない最大の整数を $\lfloor x \rfloor$ と表します。

Step 1

$\frac{a}{b}, \frac{c}{d} \in S,\ \gcd(a, b) = 1,\ \gcd(c, d) = 1,\ \frac{a}{b} < \frac{c}{d}$ のとき、$\frac{c}{d} - \frac{a}{b} = \frac{bc-ad}{bd} \ge \frac{1}{M^2}$ が成り立ちます。
これを利用して、次のような決め打ち二分探索を行います。

$x$ を $0$ 以上 $NM^2$ 以下の整数とする。「 $S$ の要素で $x/M^2$ 以下であるものが $K$ 個以上ある（☆）」が成立する最小の $x$ を $res$ とすると、
$\frac{res-1}{M^2} < y \le \frac{res}{M^2}$ を満たす唯一の $y \in S$ が答えになる。（$\frac{res}{M^2}$ 以下の要素は $K$ 個以上、$\frac{res-1}{M^2}$ 以下の要素は $K$ 個未満）

探索範囲は $x = 0, ..., NM^2$ とします。 $x = 0$ で（☆）は常に不成立、$x = NM^2$ では-1のケースを先に取り除けば常に成立します。
Writer解では $\mathrm{ok} = NM^2,\ \mathrm{ng} = 0$ から始めるめぐる式二分探索を採用しています。

二分探索の結果 $res$ から $y$ を求めます。判定(Step 2)に各回 $O(M)$ 以上かけるため、 $y$ は $O(M)$ かけて求めてもボトルネックにはなりません。
$\frac{res-1}{M^2} < \frac{a}{b} \le \frac{res}{M^2}$ となる整数 $a$ が存在するような $b$ を、$1$ から順に試して求めます。
これは$\lfloor \frac{(res-1) \cdot b}{M^2} \rfloor < \lfloor \frac{res \cdot b}{M^2} \rfloor$ であればよく、このとき $a=\lfloor \frac{res \cdot b}{M^2} \rfloor$ です。

Step 2

図1 : 判定問題の例（$N = 3, M = 6$, 緑線は$y = \frac{2}{3}x$。×印は座標が互いに素でないため除く。）

$S$ の要素で $x/M^2$ 以下であるものを数えます。図1のように表すと見通しが良くなります。
まず、互いに素という条件を無視して求めます。
$f(s, n, m)$ を「格子点 $(x, y)$ で $1 \le x \le m,\ 1 \le y \le n,\ y \le sx$ を満たすものの個数」と定義します。
$f(s, n, m)$ は、$s \le n/m$ であれば $\sum_{i=1}^{m}{\lfloor si \rfloor}$、$s > n/m$ であれば $n(m - \lfloor \frac{n}{s} \rfloor) + \sum_{i=1}^{\lfloor n/s \rfloor}{\lfloor si \rfloor}$ となります。
$\Sigma$の項はfloor_sumの形ですが、$M$ 回求めることになるため愚直に累積和を準備すればよいです。

$f(s, n, m)$ のうち $x, y$ がともに $d$ の倍数である格子点の数は、図1の全体を $1/d$ 倍に縮小して $f(s, \lfloor n/d \rfloor, \lfloor m/d \rfloor)$ で求められます。
ここから、互いに素という条件を無視しない個数を次のように約数系包除原理で求めます。

points[1..M] := 互いに素という条件を無視しない格子点数
for (i = M; i >= 1; i--) {
    // '/'は小数点以下切り捨て
    points[i] = f(s, N / i, M / i);
    for (j = i * 2; j <= M; j += i) {
        points[i] -= points[j];
    }
}

実行後、points[1]が求める要素数となります。

Writer解において、Step 2の計算量は約数包除がネックであり $O(M \log M)$、Step 1と合わせた計算量は$O(M \log M (\log N + \log M))$となります。

実装

def solve():
    # Step 2
    def count_rational(x):
        floor_sums = [0] * (M + 1)
        points = [0] * (M + 1)
        for i in range(1, M + 1):
            floor_sums[i] = floor_sums[i - 1] + x * i // (M * M)
        for i in range(M, 0, -1):
            P = (M * M * N) // (x * i)
            if x <= M * N:
                points[i] = floor_sums[M // i]
            else:
                points[i] = floor_sums[P] + (N // i) * (M // i - P)
            for j in range(i * 2, M + 1, i):
                points[i] -= points[j]
        return points[1]

    def check(mid):
        return count_rational(mid) >= K

    # https://aotamasaki.hatenablog.com/entry/meguru_bisect
    def meguru_bisect(ok, ng):
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if check(mid):
                ok = mid
            else:
                ng = mid
        return ok

    # Step 1
    N, M, K = map(int, input().split())
    if not check(N * M * M):
        print(-1)
        return
    res = meguru_bisect(N * M * M, 0)
    ans_num = -1
    ans_denom = -1
    for i in range(1, M + 1):
        if (res - 1) * i // (M * M) < res * i // (M * M):
            ans_num = res * i // (M * M)
            ans_denom = i
            break
    assert ans_num != -1
    if ans_denom == 1:
        print(ans_num)
    else:
        print(ans_num, '/', ans_denom, sep='')


if __name__ == '__main__':
    T = int(input())
    for _ in range(T):
        solve()