#include <fstream>

using namespace std;

ifstream fin ("oak.in");
ofstream fout ("oak.out");

int Euclid (int a, int b, int& x, int& y);

int main()
{int a, b, c, d, x, y, n, i, tot, k, ceva, meh1, meh2, j, m, minim, v[10000];
 fin>>n;
 for (i=0; i<n; i++)
     {fin>>a>>b>>c; tot=0; j=0;
     d=Euclid (a, b, x, y);
     if (c%d) fout<<"-1\n";
        else
        {ceva=c/d;
         for (k=c*-1; k<c; k++)
            {meh1=x*ceva+k*b/d;
             meh2=y*ceva-k*a/d;
             if (meh1>0 && meh2>0)
                {tot=1;
                 v[j]=meh1+meh2;
                 j++;
                }
            }
         m=j;
         minim=v[0];
         if (tot==0)
            fout<<"-1\n";
            else
            {for (j=1; j<m; j++)
                if (minim>v[j])
                    minim=v[j];
             fout<<minim<<'\n';
            }
        }
     }
    return 0;
}
int Euclid (int a, int b, int& x, int& y)
{int d, x1, y1;
 if (b==0)
    {x=1;
     y=0;
     return a;
    }
    else
    {d=Euclid (b, a%b, x1, y1);
     x=y1; y=x1-y1*(a/b);
     return d;
    }

}