#include <bits/stdc++.h>
//#include <chrono>
//#pragma GCC optimize("O3")
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()

using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;

ll N,M,H,W,Q,K,A,B;
string S;
using P = pair<ll, ll>;
const ll INF = (1LL<<60);

template<class T> bool chmin(T &a, const T &b){
    if(a > b) {a = b; return true;}
    else return false;
}
template<class T> bool chmax(T &a, const T &b){
    if(a < b) {a = b; return true;}
    else return false;
}
template<class T> void my_printv(std::vector<T> v,bool endline = true){
    if(!v.empty()){
        for(std::size_t i{}; i<v.size()-1; ++i) std::cout<<v[i]<<" ";
        std::cout<<v.back();
    }
    if(endline) std::cout<<std::endl;
}

bool ok(int n){
    for(int p : {10, 8}) {
        int cn = n;
        while (cn) {
            if (cn % p == 7) return false;
            cn /= p;
        }
    }
    return true;
}

ll extgcd(ll a, ll b, ll &x, ll &y){
    if(a < b) swap(a, b);
    ll d = a;
    if(b != 0){
        d = extgcd(b, a%b, y, x);
        y -= (a/b) * x;
    }else{
        x=1;
        y=0;
    }
    return d;
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin>>Q;
    rep(_, Q){
        cin>>N>>M>>K;
        K %= N;
        K %= N;
        if(K == 0){
            cout<<-1<<endl;
            continue;
        }
        M = N - M;

        ll x, y;
        ll g = extgcd(N, K, x, y);
        if(M%g != 0){
            cout<<-1<<endl;
            continue;
        }
        K /= g; M /= g; N /= g;
        if(x<0) x += N;
        if(y<0) y += N;
        if(K*x == 1) M *= x;
        else M *= y;
        cout<<M%N<<endl;
        /*
        sm = M / mkgcd;
        sk = K / mkgcd;
        ll g = extgcd(max(N, sk), min(N, sk), x, y);
        if(g != 1){
            cout<<-1<<endl;
        }else{
            if(N > sk) swap(x, y);
            //cout<<x<<' '<<y<<endl;
            if(x < 0) x += N;
            assert((sk * x)%N == 1);
            (sm *= x)%=N;
            ll res = N - sm;
            g = extgcd(max(N, K), min(N, K), x, y);
            res %= (N / g);
            cout<<res<<endl;
        }
         */
    }
}

#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;

#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define MAX 100050

#define ll long long
#define ld long double
#define lli long long int

#define pb push_back
#define INF 100000000000000
#define mod 998244353

// trignometric function always give value in Radians only
#define PI acos(-1) //3.1415926535897932384626433832795028
#define dsin(degree) sin(degree*(PI/180.0))
#define dcos(degree) cos(degree*(PI/180.0))
#define dtan(degree) tan(degree*(PI/180.0))

#define rsin(radian) sin(radian)
#define rcos(radian) cos(radian)
#define rtan(radian) tan(radian)

#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define memf(a) memset(a,false,sizeof(a))

#define loop(i,n)  for (lli i = 0; i < n; i++)
#define FOR(i,a,b) for (lli i = a; i < b; i++)

#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define makeuniq(v) v.resize(unique(all(v)) - v.begin()); //only uniq element in vector after this
#define sz(x) int(x.size())
#define F first
#define S second

#define mii map<lli,lli>

#define pii pair<lli,lli>

#define vi vector<lli>
#define vvi vector<vi>
#define vpi vector<pii>
#define vbool vector<bool>

#define seti set<lli>

#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) (a/gcd(a,b))*b
#define abs(x) ((x < 0)?-(x):x)

#define endl '\n'

template <typename Head>
void print(Head&& head)
{
    cout<<head<<endl;
}
template <typename Head, typename... Tail>
void print(Head&& head, Tail... tail)
{
    cout<<head<<" ";
    print(tail...);
}

#define scanarr(a,n) for(lli i=0;i<n;i++)    cin>>a[i];
#define scanvec(a,n) for(lli i=0;i<n;i++){ lli x ; cin>>x; a.pb(x);}

#define printarr(a,n) for(lli i=0;i<n;i++)   cout<<a[i]<<" "; cout<<endl;
#define printvec(vec) for(auto xt : vec) cout<<xt<<" ";    cout<<"\n";

#define FD(N) fixed<<setprecision(N)

#define deb(x) cout<<#x<<" "<<x<<endl;

/*
1D vector -  vi dp(n,value);
*/

ll modmul(ll a, ll b,lli MOD =  mod) {
    return ((a%MOD) * (b%MOD)) % MOD;
}

ll modadd(ll a , ll b){
    return((a%mod)+(b%mod)+mod)%mod;
}

ll modsub(ll a , ll b){
    return((a%mod) - (b%mod) + mod)%mod;
}

lli fastexpo(lli a,lli b ,lli MOD = mod){
    a = a%MOD;
    //b = b%(mod-1); // if mod is prime then only
    lli ans=1;
    while(b){
        if(b&1)
            ans=(ans*1ll*a)%MOD;
        a=(a*1ll*a)%MOD;
        b=b/2;
        }
    return ans;
 }

lli phi(lli n)
{
    lli result = n;
    for (lli p = 2; p * p <= n; ++p) {
        if (n % p == 0) {
            while (n % p == 0)
                n /= p;
            result -= result / p;
        }
    }
    if (n > 1)
        result -= result / n;
    return result;
}

int main(){
fastio
lli t=1;
cin>>t;
while(t--) {
    lli n,s,k;
    cin>>n>>s>>k;
//    we have to find i such that (k*i)%n = n-s;
// on compaaring ax %n = b where a , b , n are knows  => x = b.a^(-1) %n and a^(-1)%n = a^(phi(n)-1)%n 
//we have a = k , x = i , n = n , b = n-s;
//https://cp-algorithms.com/algebra/linear_congruence_equation.html
//https://cp-algorithms.com/algebra/module-inverse.html
lli a = k;
lli b = n-s;
    if(gcd(a,n)==1)
    {
        lli ans = modmul(b,fastexpo(a,phi(n)-1,n),n);
        print(ans);
    }
    else
    {
        lli g = gcd(a,n);
        if(b%g)
            print(-1);
        else
        {
            a/=g;
            b/=g;
            n/=g;
            lli ans = modmul(b,fastexpo(a,phi(n)-1,n),n);
            print(ans);
        }
    }
}
return 0;
}