Q=int(input()) X=[0]*Q for i in range(Q): A,B,C=map(int,input().split()) if C==1: X[i]=-1 continue Memo={0:0} def f(x): if x in Memo: return Memo[x] if x%C: T=(x//C)*C M=min(f(T)+1,(x+C-2)//(C-1)) else: M=min(f(x//C)+1,(x+C-2)//(C-1)) Memo[x]=M return M X[i]=f(A)*B print(*X,sep="\n")