#include int ri() { int n; scanf("%d", &n); return n; } // @param n `n < 2^32` // @param m `1 <= m < 2^32` // @return sum_{i=0}^{n-1} floor((ai + b) / m) (mod 2^64) unsigned long long floor_sum_unsigned(unsigned long long n, unsigned long long m, unsigned long long a, unsigned long long b) { unsigned long long ans = 0; while (true) { if (a >= m) { ans += n * (n - 1) / 2 * (a / m); a %= m; } if (b >= m) { ans += n * (b / m); b %= m; } unsigned long long y_max = a * n + b; if (y_max < m) break; // y_max < m * (n + 1) // floor(y_max / m) <= n n = (unsigned long long)(y_max / m); b = (unsigned long long)(y_max % m); std::swap(m, a); } return ans; } // @param m `1 <= m` // @return x mod m constexpr long long safe_mod(long long x, long long m) { x %= m; if (x < 0) x += m; return x; } long long floor_sum(long long n, long long m, long long a, long long b) { assert(0 <= n && n < (1LL << 32)); assert(1 <= m && m < (1LL << 32)); unsigned long long ans = 0; if (a < 0) { unsigned long long a2 = safe_mod(a, m); ans -= 1ULL * n * (n - 1) / 2 * ((a2 - a) / m); a = a2; } if (b < 0) { unsigned long long b2 = safe_mod(b, m); ans -= 1ULL * n * ((b2 - b) / m); b = b2; } return ans + floor_sum_unsigned(n, m, a, b); } int gcd(int a, int b) { while (a && b) { if (a > b) a %= b; else b %= a; } return a + b; } int main() { int t = ri(); for (int i = 0; i < t; i++) { int p = ri(); int q = ri(); int k = ri(); int g = gcd(p, q); p /= g; q /= g; int64_t lcm = p * q; int64_t lcm_cnt = floor_sum(p, p, q, p + q - 1); // std::cerr << lcm_cnt << std::endl; if (k <= lcm_cnt) { int64_t l = -1; int64_t r = lcm; while (r - l > 1) { int64_t m = l + ((r - l) >> 1); uint64_t t0 = m / p; uint64_t t1 = m / q; if (t0 * t1 / t0 != t1 || t0 * t1 >= 1000000000000) { r = m; continue; } int64_t s = m / p; int64_t cur = floor_sum(s + 1, q, p, m - s * p) + s; // std::cerr << m << " " << cur << std::endl; if (cur < k) l = m; else r = m; } printf("%" PRId64 "\n", r * g); } else { k -= lcm_cnt; printf("%" PRId64 "\n", (lcm + k) * g); } } return 0; }