#include<bits/stdc++.h>
#define rep(i,a,...) for(int i = (a)*(strlen(#__VA_ARGS__)!=0);i<(int)(strlen(#__VA_ARGS__)?__VA_ARGS__:(a));++i)
#define per(i,a,...) for(int i = (strlen(#__VA_ARGS__)?__VA_ARGS__:(a))-1;i>=(int)(strlen(#__VA_ARGS__)?(a):0);--i)
#define foreach(i, n) for(auto &i:(n))
#define all(x) (x).begin(), (x).end()
#define bit(x) (1ll << (x))
#define lambda(RES_TYPE, ...) (function<RES_TYPE(__VA_ARGS__)>)[&](__VA_ARGS__) -> RES_TYPE
#define method(FUNC_NAME, RES_TYPE, ...) function<RES_TYPE(__VA_ARGS__)> FUNC_NAME = lambda(RES_TYPE, __VA_ARGS__)
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
//const ll MOD = (ll)1e9+7;
const ll MOD = 998244353;
const int INF = (ll)1e9+7;
const ll INFLL = (ll)1e18;
template<class t>
using vvector = vector<vector<t>>;
template<class t>
using vvvector = vector<vector<vector<t>>>;
template<class t>
using priority_queuer = priority_queue<t, vector<t>, greater<t>>;
template<class t, class u> bool chmax(t &a, u b){if(a<b){a=b;return true;}return false;}
template<class t, class u> bool chmin(t &a, u b){if(a>b){a=b;return true;}return false;}
#ifdef DEBUG
#define debug(x) cout<<"LINE "<<__LINE__<<": "<<#x<<" = "<<x<<endl;
#else
#define debug(x) (void)0
#endif

namespace templates{
  ll modpow(ll x, ll b,ll mod=MOD){
    ll res = 1;
    while(b){
      if(b&1)res = res * x % mod;
      x = x * x % mod;
      b>>=1;
    }
    return res;
  }

  ll modinv(ll x){
    return modpow(x, MOD-2);
  }

  bool was_output = false;
  template<class t>
  void output(t a){
    if(was_output)cout << " ";
    cout << a;
    was_output = true;
  }
  void outendl(){
    was_output = false;
    cout << endl;
  }
  ll in(){
    ll res;
    cin >> res;
    return res;
  }

  template<class t>
  istream& operator>>(istream&is, vector<t>&x){
    for(auto &i:x)is >> i;
    return is;
  }

  template<class t, class u>
  istream& operator>>(istream&is, pair<t, u>&x){
    is >> x.first >> x.second;
    return is;
  }

  template<class t>
  t in(){
    t res; cin >> res; return res;
  }

  template<class t>
  void out(t x){
    cout << x;
  }

  template<class t>
  vector<t> sorted(vector<t> line,function<bool(t,t)> comp=[](t a,t b){return a<b;}){
    sort(line.begin(),line.end(),comp);
    return line;
  }

  template<class t>
  vector<t> reversed(vector<t> line){
    reverse(line.begin(),line.end());
    return line;
  }
}

using namespace templates;

template< typename T >
T extgcd(T a, T b, T &x, T &y) {
    T d = a;
    if(b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1;
        y = 0;
    }
    return d;
}

ll gcd(ll a,ll b){
    if(b)return gcd(b,a%b);
    return a;
}

ll func(){
    ll n = in();
    ll s = in();
    ll k = in();
    set<ll> used;
    ll x;
    ll y;
    if(s % gcd(n,k))return -1;
    y %= k / gcd(n,k);
    y += k / gcd(n,k);
    y %= k / gcd(n,k);
    extgcd(k,n,x,y);
    ll res = s / gcd(n,k) * ((y * n - gcd(n,k)) / k);
    res %= n / gcd(n,k);
    res += n / gcd(n,k);
    res %= n / gcd(n,k);
    return res;
}

int main(){
    int t = in();
    rep(i,t){
        cout << func() << endl;
    }
  return 0;
}

#include <iostream>

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

int main()
{
  int T;
  std::cin>>T;

  for(int i=0;i<T;i++)
  {
    int64_t N,S,K;
    std::cin>>N>>S>>K;

    int64_t result=0;

    int64_t x,y;
    int64_t d=gcd(K,-N,x,y);
    if(S%d==0)
    {
      x*=-S/d;
      x%=N/d;if(x<0)x+=N/d;
      result=x; 
    }
    else
    {
      result=-1;
    }

    std::cout<<result<<std::endl;
  }

  return 0;
}