for _ in range(int(input())):
    a,b,c=map(int,input().split())
    if c==1 :
        print(-1)
        continue
    d=[]
    ans=0;p=-1
    while a:
        p+=1
        d.append(a%c)
        a//=c
    ans+=p*b
    c-=1
    for i in range(1,len(d)):
    	if d[i-1] and d[i] and (d[i-1]+d[i]+c-1)//c<3:
    		d[i-1]+=d[i];d[i]=0
    for i in d:
        ans+=(i+c-1)//c*b
    print(ans)