#include <algorithm>
#include <array>
#include <cstdio>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

using namespace std;
#define int long long
#define ll long long
#define pii std::pair<int, int>
#define pdd std::pair<double, double>
#define INF (1LL << 33)
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define SHOW(p) \
    if (test)   \
        cout << #p " : " << p << endl;
bool test = false;
template <class T>
[[maybe_unused]] T ext_gcd(T a, T b, T& x, T& y) {
    // returns gcd(a,b)
    // ax + by = gcd(a,b)
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    T d = ext_gcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
};
int T, N, S, K, x, y, gcd;
signed main()
{
    // test = true;
    cin >> T;
    REP(i, T)
    {
        x = y = 0;
        cin >> N >> S >> K;
        gcd = ext_gcd(N, K, x, y);
        SHOW(gcd);
        y *= -1;
        if (test)
            cout << "x: " << x << " y: " << y << endl;
        if (S % gcd == 0) {
            y *= (S / gcd);
            if (test)
                cout << y << " " << N / gcd << endl;

            y %= (N / gcd);
            if (y < 0) {
                y += N / gcd;
            }
            cout << y << endl;
        } else {
            // NO
            cout << -1 << endl;
        }
        if (test)
            cout << endl;
    }
    return 0;
}

#include<iostream>
#include<cstdio>
#include<cmath>

using namespace std;

typedef long long ll;

ll exgcd(ll a,ll b,ll &x,ll &y)//扩展欧几里得算法
{
    if(b==0)
    {
        x=1;y=0;
        return a;  //到达递归边界开始向上一层返回
    }
    ll r=exgcd(b,a%b,x,y);
    ll temp=y;    //把x y变成上一层的
    y=x-(a/b)*y;
    x=temp;
    return r;     //得到a b的最大公因数
}

int main()
{
    int t; cin >> t;
    while(t--) {
        ll n, s, k;
        cin >> n >> s >> k;
        ll x, y;
        ll r = exgcd(n, -k, x, y);
        // cout << r << " " << x << " " << y << endl;
        y = y * s / r;
        ll t = n / r;
        if(t < 0) t = -t;
        if(s % r != 0) cout << -1 << endl;
        else cout << (y % t + t) % t << endl;
    }
    return 0;
}