lg = 40
mod = 998244353

def is_big(a, b, c, d):
  if a * d > b * c:
    return True
  return False

def solve():
  a, b, c = map(int, input().split())
  v = [0] * lg
  state = 1
  for i in range(lg):
    if i > 0:
      v[i] = v[i - 1]
    while state % c == 0:
      state //= c
      v[i] += 1
    state *= a
  if v[lg - 1] == 0:
    print(0)
    return
  arg = 1
  for i in range(2, lg):
    if is_big(v[i], i, v[arg], arg):
      arg = i
  print(((v[arg] * b) // arg) % mod)

t = int(input())
for i in range(t):
  solve()