Q = int(input())
for _ in range(Q):
    A,B,C = map(int, input().split())
    if C == 1:
        print(-1)
        continue

    cnt = 0
    while A > 0:
        if A < 2*C:
            A -= C-1
        elif A%C == 0:
            A //= C
        else:
            A -= A%C
        cnt += 1
            
    print(B*cnt)