#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();
}

/*  -*- coding: utf-8 -*-
 *
 * e.cc: E - Throne
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

/* typedef */

typedef long long ll;

/* global variables */

/* subroutines */

void exgcd(ll x, ll y, ll &a, ll &b, ll &c) {
  ll r0 = x, r1 = y;
  ll a0 = 1, a1 = 0;
  ll b0 = 0, b1 = 1;

  while (r1 > 0) {
    ll q1 = r0 / r1;
    ll r2 = r0 % r1;
    ll a2 = a0 - q1 * a1;
    ll b2 = b0 - q1 * b1;
    r0 = r1, r1 = r2;
    a0 = a1, a1 = a2;
    b0 = b1, b1 = b2;
  }
  c = r0;
  a = a0;
  b = b0;
}

/* main */

int main() {
  int tn;
  scanf("%d", &tn);

  while (tn--) {
    int n, s, k;
    scanf("%d%d%d", &n, &s, &k);

    // s + ik == 0(mod n) -> s+ik=jn -> jn-ik=s

    ll a, b, c;
    exgcd(n, k, a, b, c);
    //printf("%d*%lld+%d*%lld=%lld\n", n, a, k, b, c);

    if (s % c != 0) puts("-1");
    else {
      b *= -s / c;
      ll d = n / c;
      while (b < 0) b = b % d + d;
      while (b >= d) b %= d;
      printf("%lld\n", b);
    }
  }
  return 0;
}
