#include "bits/stdc++.h"
using namespace std;

#define int long long

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

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int T;
    cin >> T;
    while (T--) {
        int n, s, k;

        cin >> n >> s >> k;
        int x, y;
        int g = extgcd(k, n, x, y);

        if (s % g != 0) {
            cout << -1 << endl;
            continue;
        } else if (g == 1) {
            cout << (x * (-s) % n + n) % n << endl;
        } else {
            n /= g;
            s /= g;
            k /= g;
            cout << (x * (-s) % n + n) % n << endl;
        }
    }
}

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

tuple<long long, long long, long long> extgcd(long long a, long long b) {
    if (b == 0) return {a, 1, 0};
    auto [d, x, y] = extgcd(b, a % b);
    return {d, y, x - a / b * y};
}

// ax ≡ b (mod n) を満たす最小の非負整数 x を返す
// ただし、解が存在しない場合は -1 を返す
long long mod_linear_equation(long long a, long long b, long long n) {
    assert(a > 0 && n > 0);
    auto [d, x, y] = extgcd(a, n);
    n /= d;
    return b % d == 0 ? ((b / d * x) % n + n) % n : -1;
}

void solve() {
    int n, s, k;
    cin >> n >> s >> k;
    long long x = mod_linear_equation(k, -s, n);
    cout << x << '\n';
}

int main() {
    int t;
    cin >> t;
    while (t--) solve();
}