#line 1 "Main.cpp"

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#line 2 "nachia\\math\\floor-sum.hpp"

#include <cassert>
#include <utility>

namespace nachia{


// a : any value
// mod != 0
std::pair<long long, unsigned long long> SafeDiv(long long a, unsigned long long mod){
    using u64 = unsigned long long;
    if(a >= 0) return std::make_pair(0, (u64)a);
    if(mod >= (u64)1 << 62) return std::make_pair(-1, (u64)a + mod);
    long long q = a / mod;
    long long m = a % (long long)mod;
    if(m){ q--; m += mod; }
    return std::make_pair(q, m);
}

unsigned long long nC2Uint64(unsigned long long n){
    return (n%2) ? ((n-1)/2*n) : (n/2*(n-1));
}

// n : any
// 1 <= m
// a : any
// b : any
// n * a%m + b%m < 2**64
unsigned long long FloorSumU64Unsigned(
    unsigned long long n,
    unsigned long long m,
    unsigned long long a,
    unsigned long long b
){
    using u64 = unsigned long long;
    assert(1 <= m);
    u64 ans = 0;
    while(n){
        if(a >= m){
            ans += a / m * nC2Uint64(n);
            a %= m;
        }
        if(b >= m){
            ans += b / m * n;
            b %= m;
        }
        u64 y_max = a * n + b;
        if (y_max < m) return ans;
        n = y_max / m;
        b = y_max % m;
        y_max = a; a = m; m = y_max;
    }
    return ans;
}

// n : any
// 1 <= m
// a : any
// b : any
// (n+1) * m < 2**64
unsigned long long FloorSumU64Signed(
    unsigned long long n,
    unsigned long long m,
    long long a,
    long long b
){

    using u64 = unsigned long long;
    auto ua = SafeDiv(a, m);
    auto ub = SafeDiv(b, m);
    u64 ans = FloorSumU64Unsigned(n, m, ua.second, ub.second);
    ans += ua.first / m * nC2Uint64(n);
    ans += ub.first / m * n;
    return ans;
}


//
//  a i + b j < n  
//      ---+     
//       >         ( c i + d j + e )
//      ---+   
//    0 <= i, j
//
// - 0 <= n,a,b
template<class modint>
modint FloorSumTimesLinear(
    long long n,
    long long a,
    long long b,
    modint c,
    modint d,
    modint e
){
    if(n <= 0) return modint(0);
    if(a < b) return FloorSumTimesLinear(n, b, a, d, c, e);

    // eliminate triangle
    long long maxi = (n - 1) / a + 1;
    modint offset = 0;
    offset += c * modint(maxi) * modint(maxi-1) * modint(maxi+1) / modint(6);
    offset += d * modint(maxi) * modint(maxi-1) * modint(maxi+1) / modint(6);
    offset += e * modint(maxi) * modint(maxi+1) / modint(2);
    return offset + FloorSumTimesLinear(n-maxi*b, b, a-b, d, c-d, e+d*modint(maxi));
}

} // namespace nachia
#line 8 "Main.cpp"

using namespace std;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
#define rep(i,n) for(int i=0; i<(int)(n); i++)

u64 GCD(u64 a, u64 b){
    if(b == 0) return a;
    return GCD(b, a%b);
}

int main(){
    int T; cin >> T;
    rep(i,T){
        u64 P,Q,K; cin >> P >> Q >> K;
        u64 g = GCD(P,Q); P /= g; Q /= g;
        if(P > Q) swap(P,Q);
        u64 l = 0, r = P*Q+1;
        auto f = [&](u64 N) -> u64 {
            return nachia::FloorSumU64Unsigned(N/P+1, Q, P, N%P) + (N/P);
        };
        while(l + 1 < r){
            u64 N = (l+r)/2;
            if(f(N) < K) l = N; else r = N;
        }
        if(l == P*Q) r = P*Q + (K-f(P*Q));
        cout << r << '\n';
    }
    return 0;
}


struct ios_do_not_sync{
    ios_do_not_sync(){
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    }
} ios_do_not_sync_instance;