#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll gcd(ll m, ll n) {
  if (n == 0) return m;
  else return gcd(n, m % n);
}

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

int main() {
        int T;
    cin >> T;
    ll N, S, K;
    while (T--) {
        cin >> N >> S >> K;
        ll g = gcd(K, N);
        if (g > 1 && (N - S) % g != 0) {
            cout << "-1\n";
        } else {
            ll x, y;
            extgcd(K, N, x, y);
            if (x > 0) {
                x = x - (-x / N + 1) * N;
            }
            //cout << x << "\n";
            x = -x * (S / g);
            N /= g;
            cout << x % N << "\n";
        }
    }
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(x) int(x.size())
//const int mod = 1e9 + 7;
const int inf = 2e9 + 5;
const ll linf = 9e18 + 5;
const ll ll0 = 0 * 1ll;


ll n, s, k;

ll mod;

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

    return gcd(b, a % b);
}

ll euler (ll n) {
    ll d = 2;

    ll ans = n;

    while (d * d <= n) {
        if (n % d == 0) {
            ans /= d;
            ans *= d - 1;
        }
        while (n % d == 0) {
            n /= d;
        }

        d++;
    }

    if (n > 1) {
        ans /= n;
        ans *= n - 1;
    }

    return ans;
}

ll mull(ll a, ll b) {
    return (a * b) % mod;
}

ll binpow (ll a, ll b) {
    if (b == 0) {
        return 1;
    }
    if (b % 2) {
        return mull(a, binpow(a, b - 1));
    }

    ll half = binpow(a, b / 2);
    return mull(half, half);
}

void init () {
}

void input () {
    cin >> n >> s >> k;

    s = n - s;
}

void solve() {
    ll g = gcd(n, k);

    if (s % g) {
        cout << -1 << endl;
        return;
    }

    n /= g;
    s /= g;
    k /= g;


    ll inst = n;
    ll phi = n;

    for (ll d = 2; d * d <= inst; d++) {
        if (inst % d == 0) {
            phi /= d;
            phi *= d - 1;
        }
        while (inst % d == 0) {
            inst /= d;
        }
    }
    if (inst > 1) {
        phi /= inst;
        phi *= inst - 1;
    }

    mod = n;

    ll inv = binpow(k, phi -1);
    cout << mull(s, inv) << endl;
}

void output() {
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int number_of_testcases = 1;
    cin >> number_of_testcases;
    while (number_of_testcases--) {
        init();

        input();

        solve();

        output();
    }

    return 0;
}
