#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define rep(i,n) for(int i = 0; i < (n); i++)

tuple<ll, ll, ll> extgcd(ll a, ll b) {
    if(b == 0) return {a, 1, 0};
    auto [g, x, y] = extgcd(b, a%b);
    return {g, y, x-a/b*y};
}

void solve() {
    ll n, s, k;
    cin >> n >> s >> k;
    auto [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;
}
#include<bits/stdc++.h>
#define ll long long
#define re register
#define INF 2147483647
using namespace std;

inline ll read()
{
	ll f=1,x=0;char s=getchar();
	while(s<'0'||s>'9')
	{
		if(s=='-') f=-1;
		s=getchar();
	}
	while(s>='0'&&s<='9')
	{
		x=x*10+s-48;
		s=getchar();
	}
	return f*x;
}

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

int main()
{
	int T=read();
	while(T--)
	{
		ll n=read(),s=read(),k=read();
		s=n-s;
		ll x,y;
		ll GCD=exgcd(n,k,x,y);
		if(s%GCD!=0) puts("-1");
		else
		{
			ll res=s/GCD;
			y*=res;
			y=(y%(n/GCD)+(n/GCD))%(n/GCD);
			printf("%lld\n",y);
		}
	} 
	return 0;
}