#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define sz(s) (int)(s).size()
#define all(s) s.begin(), s.end()

void Speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // #ifndef ONLINE_JUDGE
    //     freopen("input.txt", "r", stdin);
    //     freopen("output.txt", "w", stdout);
    // #endif
}

int power(int a,  int n , int m){
    if(!n)
        return 1 % m;
    int res = power(a , n / 2,m);
    res = 1LL * res * res % m;
    if(n & 1)
        res = 1LL * res * a % m;
    return res;
}

int get_k(int a , int b , int d){
    if(b == 1){
        if(a % d == 0)
            return 0;
        return -1;
    }
    d /= __gcd(a , d);
    if(d == 1)
        return 0;
    for(int k = 1; k <= 50; k++){
        d /= __gcd(d , b);
        if(d == 1)
            return k;
    }
    return -1;
}

int eGCD(int a, int b, int &x, int &y) {
 x = 1;
 y = 0;
 int nx = 0, ny = 1;
 int t, r;
 while (b) {
  r = a / b;
  t = a - r * b;
  a = b;
  b = t;
  t = x - r * nx;
  x = nx;
  nx = t;
  t = y - r * ny;
  y = ny;
  ny = t;
 }
 return a;
}

int modInv(int a, int m) {
 int mi, r;
 eGCD(a, m, mi, r);
 return (mi + m) % m;
}

void solve(){
    ll a , b , d;
    cin >> a >> b >> d;

    int rem = (-a%d + d) % d;

    int g = __gcd(b,d);
    if(rem % g){
        cout << "-1\n";
        return;
    }

    int k = get_k(a,b,d);
    if(k == -1){
        cout << k << "\n";
        return;
    }


    int _b = b / g , _d = d / g , _rem = rem / g;

    int inv = modInv(_b,_d);

    int kth = 1LL * inv * _rem % _d;
    while(kth < k)
        kth += _d;

    // cout << (kth * _b) % _d << " " << _rem  << " ~\n";
    int ans = max(k,kth);

    cout << ans << "\n";

}

int main()
{
    Speed();
    int tc = 1;
    cin >> tc;
    while (tc--)
    {
        solve();
    }
    return 0;
}