#include<bits/stdc++.h>
#define ll long long
using namespace std;
int t;ll n,s,k,d;
inline ll gcd(ll x,ll y){
	while(y^=x^=y^=x%=y);
	return x;
}
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){x=1,y=0;return a;}
    int r=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return r;
}
signed main(){
	scanf("%d",&t);
    while(t--){
        scanf("%lld%lld%lld",&n,&s,&k);
        ll c=-s,x,y,d=exgcd(k,n,x,y);
    	if(c%d)puts("-1");
    	else{
    		ll a=c/d,b=n/d;
    		printf("%lld\n",((a*x)%b+b)%b);
		}
    }
    return 0;
}
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
 
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define reps(i, s, n) for (int i = (s); i < (int)(n); ++i)
#define ZERO {puts("0"); return 0;}
#define NO {puts("No"); return 0;}
#define ALL(obj) begin(obj), end(obj)
#define pb push_back
 
template<class T> void chmin(T& a, T b) { if (a > b) a = b; }
template<class T> void chmax(T& a, T b) { if (a < b) a = b; }

ll Euler (ll x)
{
	ll ans = x;
	for (ll i = 2; i * i <= x; ++i)
	{
		if (x % i == 0) ans = ans * (i-1) / i;
		while (x % i == 0) x /= i;
	}
	if (x != 1)
		ans = ans * (x-1) / x;
	return ans;
}

ll power_mod(ll x, ll k, ll n)
{
	ll ans = 1;
	while (k > 0)
	{
		if (k & 1) ans = ans * x % n;
		x = x * x % n;
		k >>= 1;
	}
	return ans;
}

ll solve()
{
	ll n, s, k; cin >> n >> s >> k;
	s = n - s;
	ll g = __gcd(k, n);
	if (s % g) return -1;
	n /= g, s /= g, k /= g;
	ll phi = Euler(n);
	ll inv_k= power_mod(k, phi-1, n);
	return inv_k*s%n;
}

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