#include<bits/stdc++.h>

#define IOS ios::sync_with_stdio(false);cin.tie(nullptr)
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double ld;

const ll LINF=1e18;
const ll MOD=998244353;
const int INF=0x3f3f3f3f;
const int MAXN=200050;

ll gcd(ll a,ll b){
	if(b==0)return a;
	else return gcd(b,a%b);
}
ll exgcd(ll a,ll b,ll &x,ll &y){
    //注意x和y必须是引用 
    if(!b){x=1,y=0;return a;}
    ll d=exgcd(b,a%b,x,y);
    ll t=x;x=y,y=t-(a/b)*y;
    return d;//d是a和b的gcd，顺便求出来 
}
ll inv(ll a,ll b){
	ll x,y;
	exgcd(a,b,x,y);
	return (x%b+b)%b;
}
void solve(int T){
	ll n,s,k,ans;
	scanf("%lld%lld%lld",&n,&s,&k);
	ll gcdd=gcd(n,gcd(n-s,k));
	s=(n-s);
	//n/=gcdd,k/=gcdd,s=(n-s)/gcdd;
	if(gcd(n,k)!=gcdd){
		printf("-1\n");
	}else{
		ans=s*inv(k,n)%n;
		printf("%lld\n",ans/gcdd);
	}
}
signed main(){
	//IOS;
	int t=1;
	scanf("%d",&t);
	for(int i=1;i<=t;i++){
		solve(i);
	}
}
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include<algorithm>
#include<string>
#include <map>
#include <queue>
#include <stack>
#include<set>
#include<math.h>

#define DIV 1000000007
#define TE 2e5
using namespace std;
using ll = long long;
using ldb = long double;

ll gcd(ll a, ll b) {
	if (b == 0)return a;
	else return gcd(b, a % b);
}

ll exgcd(ll a, ll b, ll &x, ll &y) {
	if (b == 0) {
		x = 1, y = 0;
		return a;
	}

	ll d = exgcd(b, a % b, x, y);
	ll oldx = x, oldy = y;
	x = oldy;
	y = oldx - ((a - a % b) / b) * oldy;

	return d;

}


int main() {
	int T; cin >> T;

	
	for (int i = 0; i < T; i++) {
		ll N, S, K; cin >> N >> S >> K;
		ll x = 0, y = 0;
		ll d = exgcd(K, N, x, y);

		//printf("i=%d\n", i);
		//cout << x << " " << y << " " << d << endl;
		if (S % d)cout << -1 << endl;
		else {
			ll p = -S / d;
			x *= p, y *= -p;
			K /= d, N /= d;
			x %= N;
			x = (x + N) % N;
			//cout << x << " " << y << " "<<d<<endl;
			cout << x << endl;

		}
	}
	/*

	ll x = 0, y = 0;
	ll d = exgcd(2, -3, x, y);
	
	cout << x << " " << y << " " << d << endl;
	*/
}
