#include <cstdio>

#define LMax 1000000
#define Infinity 2000000000

using namespace std;

int GCD (int A, int B, int &X, int &Y)
{
    if (B==0)
    {
        X=1;
        Y=0;
        return A;
    }
    int X0, Y0, D;
    D=GCD (B, A%B, X0, Y0);
    X=Y0;
    Y=X0-(A/B)*Y0;
    return D;
}

int FindK (int X, int Y, int A, int B)
{
    int KX, KY, L, R;
    L=-LMax, R=LMax;
    while (L<=R)
    {
        int Mid=(L+R)/2;
        if (X+Mid*B>=0)
        {
            KX=Mid;
            R=Mid-1;
        }
        else
        {
            L=Mid+1;
        }
    }
    L=-LMax, R=LMax;
    while (L<=R)
    {
        int Mid=(L+R)/2;
        if (Y-Mid*A>=0)
        {
            KY=Mid;
            L=Mid+1;
        }
        else
        {
            R=Mid-1;
        }
    }
    if (KX<=KY)
    {
        return KX;
    }
    return Infinity;
}

int main()
{
    freopen ("oak.in", "r", stdin);
    freopen ("oak.out", "w", stdout);
    int T;
    scanf ("%d", &T);
    for (; T>0; --T)
    {
        int A, B, C;
        scanf ("%d %d %d", &A, &B, &C);
        int D, X, Y;
        D=GCD (A, B, X, Y);
        if (C%D)
        {
            printf ("-1\n");
        }
        else
        {
            X=X*(C/D), Y=Y*(C/D);
            int K=FindK (X, Y, A/D, B/D);
            if (K==Infinity)
            {
                printf ("-1\n");
            }
            else
            {
                printf ("%d\n", X+K*B/D+Y-K*A/D);
            }
        }
    }
    return 0;
}