#include <stdio.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <vector>
#include <algorithm>
#include <iostream>
#include <map>

using namespace std;
long LCM(long m, long n){
    //nPrime = 1000000007
    if (m < n){
        swap(m,n);
    }
    if (m % n == 0){
        return n;
    }
    long a = m, b = n;
    while (b > 0) {
        long t = a / b;
        a -= t * b;
        swap(a, b);
    }
    return a;    
}

long Inverse(const long m, const long n){
    //nPrime = 1000000007
    if (m % n == 0){
        return 0;
    }
    long a = m, b = n, u = 1, v = 0;
    while (b > 0) {
        long t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= n;
    if (u < 0){
        u += n;
    }
    return u;    
}

int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        long n,s,k;
        scanf("%ld %ld %ld", &n, &s, &k);
        long ilcm = LCM(n,k);
        if(s % ilcm != 0){
            printf("-1\n");
            continue;
        }
        n /= ilcm;
        s /= ilcm;
        k /= ilcm;
        long nAns = Inverse(k,n) * (n-s);
        nAns %= n;
//        printf("%ld %ld %ld\n", n, s, k);
        printf("%ld\n",nAns);
    }
    
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n-1); i >= 0; i--)
#define all(v) (v).begin(),(v).end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
template <class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
template <class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template <class T> T lcm(T a, T b) { return a/gcd(a,b)*b; }
typedef pair<int, int> P;
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;
const ll MOD = 1e9+7;

// {g,x,y}: ax+by=g
tuple<ll,ll,ll> extgcd(ll a, ll b) {
    if (b == 0) return {a,1,0};
    ll g, x, y;
    tie(g,x,y) = extgcd(b, a%b);
    return {g,y,x-a/b*y};
}

void solve() {
    ll n, s, k;
    cin >> n >> s >> k;
    ll g, x, y;
    tie(g,x,y) = extgcd(k,n);
    if (s%g != 0) {
        cout << -1 << endl;
        return;
    }
    n /= g;
    s /= g;
    k /= g;
    ll ans = ((x*-s)%n+n)%n;
    cout << ans << endl;
}

int main() {
    int t;
    cin >> t;
    rep(i,t) solve();
	return 0;
}
