Q = int(input())
for _ in range(Q):
    a,b,c=map(int,input().split())
    if c==1:
        print(-1)
    else:
        cnt = 0
        while a>0:
            if c<=a<2*c-1:
                cnt+=2
                a=0
            elif a%c>0:
                cnt+=1
                a-=a%c
            else:
                a=a//c
                cnt+=1
        print(cnt*b)