#include <iostream>
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <tuple>
#include <math.h>
#include <set>
#include <cassert>
#include <stack>
#include <bitset>
#include <map>
#include <queue>
#include <random>
#include <unordered_set>
#include <unordered_map>
 
#define pqueue priority_queue
#define pb(x) push_back(x)
#define endl '\n'
#define all(x) x.begin(), x.end()
#define int long  long
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ull> vull;
typedef vector<ll> vll;
// typedef tuple<ll, ll, ll> tiii;
typedef pair<int, int> pii;
typedef vector<pair<int, int> > vpii;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<vector<ll> > vvll;
typedef vector<char> vc;
 
const int inf = 1e9 + 228;
//const int mod = 1e9 + 7;
 
 
void fast_io() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    freopen("river.in", "r", stdin);
//    freopen("river.out", "w", stdout);
}

int gcd(int a, int b){
    return (b?gcd(b, a%b):a);
}

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

int binpow(int n, int k, int mod){
    if(!k)
        return 1;
    if(k&1)
        return binpow(n, k-1, mod) * n % mod;
    int b = binpow(n, k/2, mod);
    return b*b%mod;
}

void solve(){
    int n, s, k;
    cin >> n >> s >> k;
    int a = k;
    int b = n-s;
//    cout << a << " " << b << endl;
//    cout << b * binpow(a, n-2, n) % n << endl;
    if(b % gcd(a, n)){
        cout << -1 << endl;
    } else{
        int lol = gcd(a, n);
        a /= lol;
        b /= lol;
        int st_n = n;
        n /= lol;
        int x = b * binpow(a, phi(n)-1,  n) % n;
        int kek = (st_n - x) / n;
        x += kek * n;
        x += n;
        x %= st_n;
        cout << x << endl;
    }
    
}
 
signed main() {
    fast_io();
    srand(time(NULL));
    cout << fixed << setprecision(10);
    int q = 1;
    cin >> q;
    while (q--)
        solve();
}

#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
using namespace std;

long long extGCD(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extGCD(b, a%b, y, x);
    y -= a/b * x;
    return d;
}

int main(){
    long T;
    long long N,S,K,d,ans,x0,y0;
    cin>>T;
    for(int i=0;i<T;++i){
        cin>>N>>S>>K;
        if(S%__gcd(K,N)!=0){
            ans=-1;
        }
        else{
            d=__gcd(K,N);
            K=K/d;
            N=N/d;
            S=S/d;
            extGCD(K,N,x0,y0);
            x0%=N;
            x0=(-x0*S)%N;
            if(x0<0){
                x0+=N;
            }
            ans=x0;
        }
        cout<<ans<<endl;
    }
    return 0;
}