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