ROBOT

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define task "ROBOT"
using namespace std;
using ll = long long;
using ld = long double;

const int N = 1e5 + 2;
ll a, b, c;
ll x, y, u, v;
const ll Inf = 1e18;

void Read()
{
    cin >> a >> b >> c;
}

pair<ll, ll> Euclid(ll a, ll b)
{
    ll xa = 1, xb = 0, ya = 0, yb = 1, xr, yr;
    ll r, q;
    while (b != 0)
    {
        q = a / b;
        r = a - b * q;
        xr = xa - xb * q;
        yr = ya - yb * q;
        a = b;
        xa = xb;
        ya = yb;
        b = r;
        xb = xr;
        yb = yr;
    }
    return {xa, ya};
}

void Solve()
{
    ll d = __gcd(a, b);
    if (c % d != 0)
    {
        cout << "-1\n";
        return;
    }
    pair<ll, ll> s = Euclid(a, b);
    x = s.first;
    y = s.second;
    x *= c / d;
    y *= c / d;
    //cout << x << " " << y << "\n";
    ll p = b / d, q = -a / d;
    ll posx = (x % p + p) % p;
    y = y - (x - posx) / p * q;
    x = posx;
    //cout << x << " " << y << "\n";
    ll ans = Inf;
    if (y <= 0)
    {
        if (ans > abs(x) + abs(y))
        {
            ans = abs(x) + abs(y);
            u = x;
            v = y;
        }
    }
    ll posy = (y % abs(q) - abs(q)) % abs(q);
    x = x + (y - posy) / abs(q) * p;
    y = posy;
    //cout << x << " " << y << "\n";
    if (x >= 0)
    {
        if (ans > abs(x) + abs(y))
        {
            ans = abs(x) + abs(y);
            u = x;
            v = y;
        }
    }
    //cout << u << " " << v << "\n";
    if (ans == Inf)
    {
        cout << "-1\n";
        return;
    }
    cout << ans << "\n";
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task ".INP", "r"))
        freopen(task ".INP", "r", stdin),
            freopen(task ".OUT", "w", stdout);
    int t;
    cin >> t;
    while (t--)
        Read(),
            Solve();
}