from math import gcd, lcm # n 以下の k の倍数の個数 def f(n, k): return n // k # n 以下の数のうち、C でも D でも割り切れない数の個数 def g(n, a, b): assert a != b return n - f(n, a) - f(n, b) + f(n, lcm(a, b)) INF = 1 << 60 T = int(input()) for _ in range(T): A, B, K = map(int, input().split()) if K < A and K < B: print(K) continue lo = 1 hi = INF res = lo while lo <= hi: m = (lo + hi) // 2 cnt = g(m, A, B) if cnt <= K: lo = m + 1 res = max(res, m) else: hi = m - 1 print(res)