memo = {}
def dfs(n):
    if n<C:
        return 1
    r = n%C
    if r==0:
        memo[n] = dfs(n//C)+1
    else:
        memo[n] = min(dfs((n-r)//C)+2,dfs(n-C+1)+1)
    return memo[n]
Q = int(input())
for _ in range(Q):
    A,B,C = map(int,input().split())
    if C==1:
        print(-1)
    else:
        n = dfs(A)
        print(n*B)