Q = int(input()) for i in range(Q): A,B,C = [int(x) for x in input().split()] ans = 0 if C==1: print(A*B) break while A>C: if A%C!=0: A = A-A%C ans+=1 A = A/C ans+=1 if A==C: ans+=2 if A!=1: ans+=1 print(ans*B)