#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int t,n,s,k;
void exgcd(ll a,ll b,ll &x,ll &y){
	if(!b){
		x=1,y=0;
		return;
	}
	exgcd(b,a%b,y,x); //这里仔细体会一下,这里我们将x1赋给y,y1赋给x 
	y-=(a/b)*x;
}
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%d",&n,&s,&k);
		ll c=n-s;
		ll g=__gcd(k,n);
		if(c%g) puts("-1");
		else {
			ll x,y;
			exgcd(k,n,x,y);
			ll tmp=c/g;
			ll d=n/g;
			x*=tmp;
			x=(x%d+d)%d;
			if(c%k==0) printf("%lld\n",c/k);
			else printf("%lld\n",x);
		}
	}
	return 0;
}
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

#define rep(i,n) for (long long i = 0; i < (n); ++i)
#define DIV 1000000007 //10^9+7
#define INF LONG_MAX/3

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; }
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};




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

long lcm( long m, long n ){
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	return ((m / gcd(m, n)) * n); 
}

// {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};
}

int main(){
	ll T;
	cin >> T;
	rep(_, T) {
		ll N, S, K;
		cin >> N >> S >> K;

		ll tmpg = gcd(N, K);

		if(S%tmpg != 0) {
			cout << -1 << endl;
		} else {
			ll g, x, y;
			tie(g, x, y) = extgcd(N, K);
			S/=g;

			//cout << (y%N + N)*(S%N + N)%N << endl;
			N/=g;
			cout << ((y*-S)%N + N)%N << endl;
		}



	}


}

