#include <bits/stdc++.h>

#include <iostream>
//#include <algorithm>
// #include <iomanip>
#define ll long long
#define map unordered_map
#define set unordered_set
#define l_l pair<ll, ll>
#define vll vector<ll>
#define mll map<ll, ll>
#define mp make_pair

using namespace std;

const ll MOD = 1000000007LL;
const ll INF = (1LL << 60LL);

ll mod(ll a, ll m) {
  ll r = (a % m + m) % m;
  return r;
}

ll extGcd(ll a, ll b, ll &p, ll &q) {
  if (b == 0) {
    p = 1;
    q = 0;
    return a;
  }
  ll d = extGcd(b, a % b, q, p);
  q -= a / b * p;
  return d;
}

pair<ll, ll> crt(const vector<ll> &b, const vector<ll> &m) {
  ll r = 0, M = 1;
  for (int i = 0; i < (int)b.size(); ++i) {
    ll p, q;
    ll d = extGcd(M, m[i], p, q);
    if ((b[i] - r) % d != 0) {
      return make_pair(0, -1);
    }
    ll tmp = (b[i] - r) / d * p % (m[i] / d);
    r += M * tmp;
    M *= m[i] / d;
  }
  return make_pair(mod(r, M), M);
}

int main() {
  ll T;
  scanf("%lld", &T);

  for (ll i = 0; i < T; i++) {
    ll N, S, K;
    scanf("%lld %lld %lld", &N, &S, &K);

    auto r1 = crt({0, N - S}, {K, N});
    // cout << r1.second << "k+" << r1.first << endl;  // 15k + 8

    ll ans;
    if (r1.second <= 0) {
      ans = -1;
    } else {
      ans = r1.first / K;
    }
    cout << (ans) << endl;
    // cout << ("") << endl;
  }

  //
}

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
 
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define reps(i, s, n) for (int i = (s); i < (int)(n); ++i)
#define ZERO {puts("0"); return 0;}
#define NO {puts("No"); return 0;}
#define ALL(obj) begin(obj), end(obj)
#define pb push_back
 
template<class T> void chmin(T& a, T b) { if (a > b) a = b; }
template<class T> void chmax(T& a, T b) { if (a < b) a = b; }

// {g,x,y}: ax+by=g
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};
}
 
void solve()
{
  ll n, s, k;
  cin >> n >> s >> k;
  ll g, x, y;
  tie(g,x,y) = extgcd(k,n);
  if (s%g != 0) {
    cout << -1 << endl;
    return;
  }
  n /= g;
  s /= g;
  k /= g;
  ll ans = ((x*-s)%n+n)%n;
  cout << ans << endl;
}
 
int main() 
{
  int t; cin >> t;
  rep(i,t) solve();
}
