#include <bits/stdc++.h>

using namespace std;

#define ll long long

void solve(){
    ll p,q,e;
    cin >> p >> q >> e;

    ll tot = p * q - 1;

    for (ll i = 2;1ll * i * i <= tot;i++)if (tot % i == 0){
        if (i > p && i > q && i > e && p * q % i == 1ll){
            ll r = e * q % i;
            if (e == r * p % i){
                cout << r << "\n";
                return;
            }
        }        
        while (tot % i == 0){
            tot /= i;
        }
    }

    if (tot != 1){
        ll i = tot;
        if (i > p && i > q && i > e && p * q % i == 1ll){
            ll r = e * q % i;
            if (e == r * p % i){
                cout << r << "\n";
                return;
            }
        }        
    }
    cout << "shuanQ\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--){
        solve();
    }

    return 0;
}