#include <bits/stdc++.h>

typedef long long ll;
 
using namespace std;
 
//const int MAX=INT_MAX;
 
//const ll MAX=100000000000;
 
//const int mod = 1000000007;
//const int mod = 998244353;
 
//const ll A=100000000000;


const int INF=1000000000;

ll extgcd(ll a,ll b,ll& x,ll& y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }else{
        ll d =extgcd(b,a%b,x,y);
        ll prv=x;
        x=y;
        y=prv-a/b*y;
        return d;
    }
    
}



int main(){
    
    int T;
    cin>>T;
    
    ll N,S,K;
    
    
    for(int t=0;t<T;t++){
        cin>>N>>S>>K;
        
        ll x=0;
        ll y=0;
        ll g=extgcd(N,-K,x,y);
        if(S%g!=0){
            cout<<-1<<endl;
        }else{
            ll s=S/g;
            ll n=N/g;
            ll k=K/g;
            ll nx=x*s;
            ll ny=y*s;
            
           // cout<<"ny:"<<ny<<"n:"<<n<<endl;
           
            
            ll t;
            if(n>0){
            if(-double(ny)/double(n)<0){
                t=-ny/n;
            }else{
                t=-ny/n+1;
            }
            }else{
                if(-double(ny)/double(n)<0){
                    t=-ny/n-1;
                }else{
                    t=-ny/n;
                }
                
            }
            
           // cout<<t<<endl;
            
            
           ll ans=n*t+ny;
            
            

           // cout<<g<<":"<<s<<":"<<x<<":"<<y<<":"<<ans<<endl;
            cout<<ans<<endl;
            
        }
    }
}
   

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<utility>
#include<set>
#include<stack>
#include<list>
#include<deque>
#include<bitset>
#include<iomanip>
#include<cstring>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<cmath>
#include<cctype>


#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ren(i,a,b) for(int i=a;i>=b;i--)
#define ff first
#define ss second
#define pll pair<long long int,long long int>
#define pii pair<int,int>
#define vll vector<long long int>
#define vii vector<int>
#define gi(n) scanf("%d",&n)
#define gll(n) scanf("%lld",&n)
#define gstr(n) scanf("%s",n)
#define gl(n) cin >> n
#define oi(n) printf("%d",n)
#define oll(n) printf("%lld",n)
#define ostr(n) printf("%s",n)
#define ol(n) cout << n
#define os cout<<" "
#define on cout<<"\n"
#define o2(a,b) cout<<a<<" "<<b
#define all(n) n.begin(),n.end()
#define present(s,x) (s.find(x) != s.end())
#define cpresent(s,x) (find(all(s),x) != s.end())
#define tr(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++)
using namespace std;

typedef unsigned long long int ull;
typedef long long int ll;
typedef long double ld;
typedef vector<vector<ll> > mat;

ll gcd (ll a, ll b, ll & x, ll & y) {
	if (a == 0) {
		x = 0; y = 1;
		return b;
	}
	ll x1, y1;
	ll d = gcd (b%a, a, x1, y1);
	x = y1 - (b / a) * x1;
	y = x1;
	return d;
}

void solve()
{
	ll n,s,k,gg;
	cin>>n>>s>>k;
	gg=__gcd(n,k);
	if(s%gg!=0)
	{
		ol("-1\n");
		return;
	}
	n/=gg,s/=gg,k/=gg;
	
	ll x,y;
	gcd(k,n,x,y);
	
	x=(x+n)%n;
	
	s=(n-s)%n;
	s=(s*x)%n;
	
	s=(s+n)%n;
	
	ol(s);on;
}
int main()
{ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
cin>>t;
while(t--)
{
	solve();
}

return 0;
}

