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