#include <fstream>
using namespace std;
ifstream in("euclid3.in");
ofstream out("euclid3.out");
long long a, b, c;
int x, y, d, t;
void euclidext1(long long a, long long b, int &x, int &y, int &d){
    long long r, c, x1, y1, x2, y2;
    if(b == 0){
        x = 1;
        y = 0;
        d = a;
        return ;
    }
    x1 = 1;
    y1 = 0;
    x2 = 0;
    y2 = 1;
    r = a % b;
    c = a / b;
    while (r){
        x = x1 - x2 * c;
        x1 = x2;
        x2 = x;
        y = y1 - y2 * c;
        y1 = y2;
        y2 = y;
        a = b;
        b = r;
        r = a % b ;
        c = a / b;
    }
    d = b;
}
int main()
{
    in>>t;
    for(int i = 1; i <= t ; ++i){
        in >> a >> b >> c;
        euclidext1(a,b,x,y,d);
    out<< x%c << y%c << "\n";
    }
    return 0;
}