Q=int(input())
for _ in range(Q):
  a,b,c=map(int,input().split())
  if (a**100)%c!=0:
    print(0)
    continue
  x,y=100,1
  u=[1]*100
  v=[1]*100
  for k in range(1,50):
    u[k]=u[k-1]*a
    v[k]=v[k-1]*c
  for k1 in range(1,50):
    for k2 in range(1,50):
      if x*k2>y*k1:
        if u[k1]%v[k2]==0:
          x,y=k1,k2
  result=(y*b)//x
  result%=998244353
  print(result)