#include<atcoder/all>
using namespace std;
using ll = long long;

int main(){
    int t;
    cin >> t;
    while(t--){
        ll p, q, k, g;
        cin >> p >> q >> k;
        g = __gcd(p, q);
        p /= g, q /= g;
        if(p == 1 || q == 1){
            cout << g * k << '\n';
            continue;
        }
        auto f = [&](ll v){
            ll r = min(q, v / p + 1);
            return atcoder::floor_sum(r, q, p, v + q - p * (r - 1));
        };
        ll ng = 0, ok = 1ll << 60, mid;
        while(ng + 1 < ok){
            mid = (ng + ok) / 2;
            if(f(mid) <= k)ng = mid;
            else ok = mid;
        }
        cout << g * ok << '\n';
    }
}