#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MOD int(1e9+7)
#define INF int(1e9)
#define LINF ll(1e18)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define P pair<ll,ll>

ll gcd(ll m, ll n) {//最大公約数
    if (n == 0)return m;
    return gcd(n, m % n);
}//gcd

long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}


void solve(ll a, ll b, ll m){
  b=((b%m)+m)%m;
  ll x;
  ll d=gcd(a,m);
  if(b%d!=0) x=-1;
  else{
    a/=d; b/=d; m/=d;
    x=b*modinv(a,m)%m; 
  }
  cout<<x<<endl;
  return;
}

int main(){
  int t;cin>>t;
  ll n,s,k;
  rep(tmp,t){
    cin>>n>>s>>k;
    solve(k,-s,n);
  }
}
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author houghstc
 */

#include <iostream>
#include <fstream>

#include <iostream>
#include <vector>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
#include <cstring>
#include <climits>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <cassert>

using namespace std;
using pii = pair<int, int>;
using ll = long long;
using pll = pair<ll, ll>;

const int MOD = 1e9+7;
const double PI = std::acos(-1);

class EThrone {
public:

    ll gcd(ll a, ll b)
    {
        return b == 0 ? a : gcd(b, a%b);
    }

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

    void solveOne(std::istream& in, std::ostream& out) {
        ll n, s, k;
        in >> n >> s >> k;
        // x * k == (n-s) mod n
        // x * k + y * n = n-s
        // gcd(k, n) | (n-s)
        ll x, y;
        ll d = exgcd(k, n, x, y);
        if((n-s) % d != 0)
        {
            out << -1 << endl;
            return;
        }

        x *= (n-s)/d;
        ll r = n/d;
        x = (x % r + r) % r;
        out << x << endl;
    }
    void solve(std::istream& in, std::ostream& out) {
        int t;
        in >> t;
        while(t--) {
            solveOne(in, out);
        }
    }
};


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    EThrone solver;
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    solver.solve(in, out);
    return 0;
}
