#include<bits/stdc++.h>
using namespace std;
#define A(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define int int64_t
void _read();
int mod;
inline int inv(int a) {
  	a %= mod;
  	if (a < 0) a += mod;
  	int b = mod, u = 0, v = 1;
  	while (a) {
  		int t = b / a;
  		b -= t * a; swap(a, b);
  		u -= t * v; swap(u, v);
  	}
  	assert(b == 1);
  	if (u < 0) u += mod;
  	return u;
}
void test() {
	int n,s,k;
	cin >> n >> s >> k;
	mod = n;
	// kx == s;
	int d = __gcd(k,n);
	if(s % d) {
		cout << -1 << '\n';
		return;
	}
	k /= d;
	s /= d;
	n /= d;
	mod = n;
	s %= mod;
	k %= mod;
	int y = inv(k);
	int ans = (s * y) % mod;
	cout << mod - ans << '\n';
}
main () { _read(); 

	int tc;
	cin >> tc;
	while(tc--) test();
	return 0;
};

void _read() {
	ios_base :: sync_with_stdio(false);
	cin.tie(NULL);
	#ifdef LOCAL
	freopen("input.txt","r",stdin);
	#endif
}

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <iomanip>
#define ll long long int
#define inf 1000000000000
#define mod 1000000007

// templates
#define all(v) v.begin(),v.end()
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ps(x,y)   fixed<<setprecision(y)<<x
#define fo(i,a,b) for(int i=a;i<b;i++)
#define ro(i,a,b) for(int i=a;i>=b;i--)
#define vi vector<int>
#define vl vector<ll>
#define sc(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define pr(n) printf("%d\n",n)
#define pl(n) printf("%lld\n",n)
#define prs(n) printf("%d ",n)
#define pls(n) printf("%lld ",n)
using namespace std;

ll GCD(ll a, ll b, ll& x, ll& y) {
	if (b == 0) {
		x = 1LL;
		y = 0LL;
		return a;
	}
	ll x1, y1;
	ll d = GCD(b, a % b, x1, y1);
	x = y1;
	y = x1 - y1 * 1LL * (a / b);
	return d;
}
void solve()
{
	ll n, s, k;
	sl(n), sl(s), sl(k);
	ll x, y;
	ll gc = __gcd(n, k);
	if (s % gc) {
		pl(-1LL);
	}
	else {
		// y->loops x->moves x*k+s=y*n => (x*k-y*n=-s)
		n /= gc, s /= gc, k /= gc;
		gc = GCD(k, n, x, y);
		ll mod_inv = (x % n + n) % n;
		ll ans = ((-s * mod_inv) % n + n) % n;
		pl(ans);
	}
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	int t = 1;
	scanf("%d", &t);
	while (t--) {
		solve();
	}

}