#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>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define ll long long
#define ALL(a) (a).begin(),(a).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define Pii pair<int,int>
#define Pll pair<long long,long long>
#define fout(num) cout << fixed << setprecision(20) << (num) << endl
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
//vector<vector<ll>> dp(n,vector<ll>(n))
//2-dim:vector<vector<Type>> vv(n, vector<Type>(m, d));
//3-dim:vector<vector<vector<Type>>> vvv(n, vector<vector<Type>>(m, vector<Type>(l, d)));

using namespace std;

long long extGCD(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extGCD(b, a%b, y, x);
    y -= a/b * x;
    return d;
}

long long gcd(long long a,long long b){
    if(b==0) return a;
    return gcd(b,a%b);
}
long long lcm(long long a,long long b){
    return a/gcd(a,b)*b;
}

signed main(){
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    int test; cin >> test;
    while(test--){
        ll n,s,k; cin >> n >> s >> k;
        if(s%gcd(n,k)!=0){
            cout << -1 << endl;
            continue;
        }
        ll ggg = gcd(gcd(n,k),s);
        n/=ggg; k/=ggg; s/=ggg;



        ll gc = gcd(n,k);
        n/=gc;
        k/=gc;
        ll x,y;
        extGCD(n,k,x,y);
        //cout << x << " " << y << endl;continue;
        x *= s;
        y *= s;
        y *= gc;

        ll g = n/gc;
        
        y = -y;
        if(y>0){
            ll kk = y/g;
            y -= kk*g;
        }else if(y<0){
            ll kk = (-y)/g;
            kk++;
            y += kk*g;
        }
        cout << y << "\n";
    }
    return 0;
}
// g++ main.cpp -o a.out && ./a.out