/*/^--^\  
  \____/  
 /      \ _____  _ __  __ ____  _     ____   ____  _____ 
|        || ()_)| |\ \/ /| ===|| |__ / (__` / () \|_   _|
 \__  __/ |_|   |_|/_/\_\|____||____|\____)/__/\__\ |_|  
|^|^\ \^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|^|
| | |\ \| | | | | | | | | | | | | | | | | | | | | | | | |
#####/ /#################################################
| | |\/ | | | | | | | | | | | | | | | | | | | | | | | | |
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_| |
#include <orz/i_am_noob.h>
#include <orz/balbit.h>
#include <orz/nathanlee726.h>*/
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<ll,ll>;
using pdd=pair<double,double>;
#define int ll

#define For(i,a,b)  for(int i=a;i<=b;i++)
#define Forr(i,a,b) for(int i=a;i>=b;i--)
#define F first
#define S second

#define eb emplace_back
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define mkp make_pair

#define MOD (ll)(1000000007)
#define INF (1e15)
#define EPS (1e-6)

#ifdef LOCALMEOW
#define debug(...) do{\
	cerr << __PRETTY_FUNCTION__ << " - " << __LINE__ <<\
	" : ("#__VA_ARGS__ << ") = ";\
	_OUT(__VA_ARGS__);\
}while(0)
template<typename T> void _OUT(T x) { cerr << x << "\n"; }
template<typename T,typename...I>
void _OUT(T x,I ...tail) { cerr << x << ", "; _OUT(tail...); }
#else
#define debug(...)
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
void FASTIO(){ ios::sync_with_stdio(false); cin.tie(0); }

int gcd(int a,int b) { return b==0?a:gcd(b,a%b); }
int lcm(int a,int b) { return a/gcd(a,b)*b; }
int fpow(int b,int p){
	int ans=1,now=b;
	while(p){
		if(p&1) ans=ans*now%MOD;
		p/=2; now=now*now%MOD;
	}
	return ans;
}
void maxify(int &a,int b) { if(b>a) a=b; }
void minify(int &a,int b) { if(b<a) a=b; }

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

int32_t main(){
	FASTIO();
	//code...
	int N; cin>>N;
	int n,s,x;
	while(N--){
		cin>>n>>s>>x;
		int a,b;
		int g=gcd(x,n,a,b);
		a%=n; if(a<0) a+=n;
		//cout<<a<<" "<<a*x%n<<"\n";
		b=(a*(n-s)/g)%(n/g);
		if(b<0) b+=n;
		if((s+b*x)%n!=0) cout<<"-1\n";
		else cout<<b<<"\n";
	}
	return 0;
}
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0 ; i < (int)(n) ; i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T &a, T b) { if (a<b) {a=b; return 1;} return 0;}
template<class T> inline bool chmin(T &a, T b) { if (b<a) {a=b; return 1;} return 0;}

//ax + by = g , return {g,x,y}
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};
}

//s + kx = 0(mod n)
// x = -s*k-^1 (mod n)

void solve(){
  ll n,k,s,g,x,y;
  cin >> n >> s >> k;
  tie(g,x,y) = extGCD(k,n);
  if(s%g != 0){
    cout << -1 << endl;
    return;
  }
  n /= g;
  k /= g;
  s /= g;
  ll ans = (n+(-s*x)%n)%n;
  cout << ans << endl;
}

int main() {
  int t;
  cin >> t;
  rep(i,t){
    solve();
  }
  return 0;
}