#include "bits/stdc++.h"
#define FI first.first
#define SE first.second
#define TH second
#define fi first
#define se second
#define th second

using namespace std;

template<typename T>
string to_string(const vector<T>& vc, int w) {
	if(vc.empty()) return "";
	if(w + 1 == vc.size()) return to_string(vc[w]);
	return to_string(vc[w]) + "," + to_string(vc, w + 1);
}

template<typename T>
string to_string(const vector<T>& vc) {
	return "{" + to_string(vc, 0) + "}";
}

void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

class DebugStream {}LOG;
template <typename T>DebugStream &operator<<(DebugStream &s, const T&) { return s; }
#ifdef DEBUG
#define LOG clog
#endif

typedef long long ll;
typedef pair<ll, ll> ii;
typedef long double ld;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int maxN = 1e5 + 9, maxV = 1e6 + 9, MOD = 1e9 + 7, SQ = 335, lg = 20, bs = 29;

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	#endif

	int t;
	cin >> t;
	while(t--) {
		ll n, s, k, x, y;
		cin >> n >> s >> k;
		k %= n;
		ll gg = gcd(n, k, x, y);
		ll nm = n - s;
		if(y < 0) y = (n - abs(y) % n) % n;
		else y %= n;

		if(nm % gg) {
			cout << "-1\n"; continue;
		}
		nm /= gg;
		n /= gg;

		ll ans = nm * y % n;
		cout << ans << '\n';
	}
	
}


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
pair <ll,ll> extgcd(ll a,ll b)
{
	if (b==0) return {1,0};
	pair<ll,ll> u=extgcd(b,a%b);
	return {u.second,u.first-a/b*u.second};
	
}
ll gcd(ll x,ll y)
{
	if(y==0) return x;
	return gcd(y,x%y);
}
void solve ()
{
	ll n,s,k;
	cin>>n>>s>>k;
	if (s%gcd(n,k)!=0) cout<<-1<<endl;
	else
	{
		ll e=gcd(n,k);
		n=n/e;
		s=s/e;
		k=k/e;
		pair<ll,ll> v=extgcd(k,n);
		cout<<((-v.first*s)%n+n)%n<<endl;
	}
}
int main()
{
	int t;
	cin>>t ;
	while (t--)
	{
		solve ();
	}
	return 0;
 }