def solve(a, b, c):
    if c == 1:
        return -1
    ans = 0
    while a > 0:
        if a <= c - 1:
            ans += 1
            a = 0
        elif a <= 2 * (c - 1):
            ans += 2
            a = 0
        elif a % c == 0:
            ans += 1
            a //= c
        else:
            ans += 1
            a = a // c * c
    return ans * b

for _ in range(int(input())):
    print(solve(*map(int, input().split())))