#include <iostream>
#include <vector>
//#include <string>
#include <algorithm>
//#include <math.h>
//#include <queue>
//#include <stack>
//#include <iomanip>

// sometimes used
//#include <set>
//#include <map>
//#include <numeric>
//#include <list>
//#include <deque>
//#include <unordered_map>

typedef long long LL;
//typedef long double LD;
using namespace std;
 
//#define MOD 1000000007
//#define MOD 998244353
//#define MAX 100100
//#define NIL -1
//#define INF 1000000000000000000
//const LL SEG_VAL = 1 << 19;

LL modinv(LL a, LL m) {
    LL b = m, u = 1, v = 0;
    while (b) {
        LL t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= m;
    if (u < 0){
        u += m;
    }
    return u;
}

LL gcd(LL a, LL b){
    LL tmp; 
    if(a<b){
        tmp = a;
        a = b;
        b = tmp;
    }
    tmp = a%b;
    while(tmp!=0){
        a = b;
        b = tmp;
        tmp = a%b;
    }

    return b;
}

int main(){
    LL t;
    cin >> t;
    vector<LL> n(t);
    vector<LL> s(t);
    vector<LL> k(t);
    for(LL i=0; i<t; i++){
        cin >> n[i] >> s[i] >> k[i];
    }

    for(LL i=0; i<t; i++){
        s[i]=n[i]-s[i];
        LL d=gcd(n[i], gcd(s[i], k[i]));
        n[i]/=d;
        s[i]/=d;
        k[i]/=d;
        if(gcd(k[i],n[i])!=1){
            cout << -1 << endl;
        }else{
            cout << (s[i]*modinv(k[i], n[i]))%n[i] << endl;
        }
    }


    return 0;
}

#include <bits/stdc++.h>

using namespace std;
const int INF = 1e9 + 10;
#define ll long long 
#define lowbit(i) ((i) & -(i))


ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    ll gd = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return gd;
}

void solve()
{
    ll N, S, K;
    cin >> N >> S >> K;
   
    if (S % __gcd(K, N) == 0)
    {
        ll x, y;
        exgcd(N,K, x, y);
        ll o=S / __gcd(K, N);
        x*=o,y*=o;
        N/=__gcd(K, N);
        y=-y;
        y=(y%N+N)%N;
        
       
        cout <<y<<endl;
       
    }
    else cout << -1 << endl;
    
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T ;
    cin >>T;
    while (T--)
    {
        solve();
        
    }
}