for _ in range(int(input())):
    a,b,c=map(int,input().split())
    if c==1:
        print(-1)
        continue
    ans=0
    k=a
    x=[]
    while a:
    	if a%c:
    		ans+=b
    	x.append(a%c)
    	a//=c
    	if a:
    		ans+=b
    x.reverse()
    if len(x)>=2 and x[0]==1 and x[1]:
    	ans-=b
    print(ans)