//https://cp-algorithms.com/algebra/linear_congruence_equation.html

#include <bits/stdc++.h>
// #include <boost/multiprecision/cpp_int.hpp>

#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,b,a) for(int i=b;i>=a;i--)
#define fori(a) for(auto i : a )
#define all(a) begin(a), end(a)
#define set(a,b) memset(a,b,sizeof(a))
#define sz(a) a.size()
double pi=acos(-1);
#define ll long long
#define ull unsigned long long
#define pb push_back
#define PF push_front //deque
// #define mp make_pair
#define pq priority_queue
const ll mod=1000000007;
#define f first
#define s second
#define pii pair< ll, ll >
#define vi vector<int>
#define vpii vector<pii>
#define debug(v) for(auto i:v) cout<<i<<" ";
#define tc int t; cin >> t; while(t--)

// using namespace boost::multiprecision;
using namespace std;
void optimizeIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

ll gcdExtended(ll a, ll b, ll* x, ll* y);

// Function to find modulo inverse of a
ll modInverse(ll a, ll m)
{
    ll x, y;
    ll g = gcdExtended(a, m, &x, &y);
    return (x % m + m) % m;
}

// C function for extended Euclidean Algorithm
ll gcdExtended(ll a, ll b, ll* x, ll* y)
{
    // Base Case
    if (a == 0)
    {
        *x = 0, *y = 1;
        return b;
    }

    ll x1, y1; // To store results of recursive call
    ll gcd = gcdExtended(b % a, a, &x1, &y1);

    // Update x and y using results of recursive
    // call
    *x = y1 - (b / a) * x1;
    *y = x1;

    return gcd;
}
void solve(){
  // Method 1:(n*x+n-s)%k==0 find min x;
  // or Method 2:  (x*k+s)%n==0 find min x;
  ll n,s,k;
  cin>>n>>s>>k;
  ll b= (k+(s-n)%k)%k;
  ll a=n;
  if(b%__gcd(a,k)!=0){cout<<-1<<endl;return;}
  ll g=__gcd(a,k);
  a/=g;b/=g,k/=g;
  ll z=(b*modInverse(a,k))%k;
  cout<<(z*n+n-s)/(k*g)<<endl;
}

int main(){
    optimizeIO();
    int r=1;
    tc{solve();}
}
// Method 2:
// void solve(){
//   ll n,s,k;
//   cin>>n>>s>>k;
//   ll b=n-s;
//   ll a=k;
//   ll m=n;
//   ll d=__gcd(__gcd(a,b),m);
//   a/=d,b/=d,m/=d;
//   // cout<<a<<b<<m<<endl;
//   if(__gcd(a,m)!=1){cout<<-1<<endl;return;}
//   ll z=(b*modInverse(a,m))%m;
//   cout<<z<<endl;
// }

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