#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<string>
#include<algorithm>
#define FOR(i,a,b) for(i=(a);i<=(b);i++)
#define ROF(i,a,b) for(i=(a);i>=(b);i--)
#define mmt(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define N 10010
using namespace std;
typedef long long LL;
typedef long double LD;
struct dat{int Len;LL c[N][2];void init(){mmt(c,0);Len=0;}}rr,rt,r;
int T;LL a1[N],b1[N];
dat div(LL x)
{
  LL i;r.init();
  for(i=2;(LL)i*(LL)i<=x;i++)
  {
   if (x%i==0)
   {
     r.c[++r.Len][0]=i;
     while (x%i==0) r.c[r.Len][1]++,x/=i;
   }
 }
  if (x!=1) r.c[++r.Len][0]=x,r.c[r.Len][1]=1;
  return r;
}
LL gcd(LL x,LL y){return x%y==0?y:gcd(y,x%y);}
LL mulmod(LL x,LL p,LL Mod)
{
  LL res=0,e=x;
  for(;p;p>>=1) {res+=p&1?e:0;res%=Mod;e+=e;e%=Mod;}
  return res;
}
LL powmod(LL x,LL p,LL Mod)
{
  LL res=1,e=x;
  for(;p;p>>=1) {res=mulmod(res,p&1?e:1,Mod);e=mulmod(e,e,Mod);}
  return res;
}
LL cphi(LL x)
{
  rt=div(x);LL res=x;int i;
  FOR(i,1,rt.Len) res/=rt.c[i][0],res*=(rt.c[i][0]-1);
  return res;
}
int main()
{
  scanf("%d",&T);
  int i,j,k;LL r2,A,B,K;
  while (T--)
  {
    scanf("%lld%lld%lld",&A,&B,&K);
    a1[1]=A;b1[1]=B;i=1;
    while (1)
    {
      if (a1[i]==0) break;
      b1[i]=B/gcd(a1[i],B);
      if (gcd(b1[i],K)==1) break;
      i++;a1[i]=mulmod(a1[i-1],K,B);
    }
    printf("%d ",i-1);
    B=b1[i];
    if (B)
    {
      LL phi=cphi(B);
      rr=div(phi);
      FOR(i,1,rr.Len)
      {
        FOR(j,1,rr.c[i][1])
        {
          if (powmod(K,phi/rr.c[i][0],B)==1) phi/=rr.c[i][0];else break;
        }
      }
      r2=phi;
    }else r2=0;
    printf("%lld\n",r2);
  }
  return 0;
}