// E - Throne
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// 拡張ユークリッド互除法
// (g,x,y): ax+by=g
tuple<ll,ll,ll> extgcd(int a, int b){
	if(b==0) return {a, 1, 0};
	auto[g, x, y] = extgcd(b, a%b);
	return {g, y, x-a/b*y};
}

int solve(int n, int s, int k){
	auto[g, x, y] = extgcd(k, n);
	if(s%g) return -1;
	n /= g, s /= g, k /= g;
	return (-s * x % n + n)%n;
}

int main(){
	int t; cin>>t;
	while(t--){
		int n, s, k; cin>>n>>s>>k;
		cout<< solve(n, s, k) <<endl;
	}
}

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstdlib>
#include<queue>
#include<set>
#include<cstdio>
#include<map>
#include<cassert>

using namespace std;

#define ll long long
#define reps(i, a, b) for(int i = a; i < b; i++)
#define rreps(i, a, b) for(int i = a-1; i >= b; i--)
#define rep(i, n) reps(i, 0, n)
#define rrep(i, n) rreps(i, n, 0)
#define P pair<int, int>
#define vec vector<int>
#define mat vector<vector<int> >

const ll mod = 1000000007;
const int INF = 1001001001;

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

void solve() {
    ll n, s, k;
    cin >> n >> s >> k;
    ll g, x, y;
    g = extgcd(k, n, x, y);
    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();
    }
}