import sys
input=lambda: sys.stdin.readline().rstrip()
q=int(input())
for _ in range(q):
	a,b,c=map(int,input().split())
	if c==1:
		print(-1)
	else:
		ans=0
		while a>0:
			if c<a<=2*(c-1) and a%c:
				ans+=2
				break		
			if a%c!=0 and a//c>0:
				ans+=1
			a//=c
			ans+=1
		print(ans*b)