T=int(input())
for _ in range(T):
  a,b,c=map(int,input().split())
  if c==1:
    print(a*b)
    continue
  d=[]
  while a>0:
    d+=1+(a%c!=0)
    a//=c
  print((d-1)*b)