#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <queue>

#define lc u << 1
#define rc u << 1 | 1

using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
LL n,s,k;

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

void solve()
{
    scanf("%lld%lld%lld",&n,&s,&k);
    LL x,y;
    LL d = exgcd(k,n,x,y);
    n /= d;
    if(s % d) puts("-1");
    else
    {
        printf("%lld\n",(-x * (s / d) % n + n) % n);
    }
}

int main()
{
    #ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #else

    #endif // LOCAL
    int T = 1;
    scanf("%d",&T);
    while(T --)
    {
        solve();
    }
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll n, ll m){
  if(n < m) swap(n, m);
  if(n % m == 0) return m;
  return gcd(m, n % m);
}
ll extgcd(ll a, ll b, ll& x, ll& y){
	if (b == 0) {
    	x = 1;
    	y = 0;
    	return a;
  	}
  	ll gcd = extgcd(b, a % b, x, y);
  	ll oldX = x;
  	x = y;
  	y = oldX - a / b * y;
  	return gcd;
}
int main(){
  int t;
  cin >> t;
  for(int loop = 0; loop < t; loop++){
    ll n, s, k, x, y;
    cin >> n >> s >> k;
    ll g = gcd(n, k);
    if(s % g != 0){
      cout << -1 << "\n";
      continue;
    }
    n /= g; k /= g; s /= g;
    int a = extgcd(n, k, x, y);
    x *= s; y *= s;
    //cout << n << " " << x << " " << k << " " << y << " " << s << " ";
    if(y < 0) y %= n;
    if(y > 0){
      y -= (y / n) * n;
    }
    if(y > 0) y -= n;
    cout << -y << "\n";
  }
}