Q=int(input())

for testcases in range(Q):
    A,B,C=map(int,input().split())

    if C==1:
        print(-1)
        continue

    count=0
    while A>(C-1)*2:
        if A%C==0:
            A//=C
            count+=1

        else:
            A=A//C*C
            count+=1

        #print(A)

    if A<C:
        count+=1
    else:
        count+=2

    print(count*B)