import sys
sys.setrecursionlimit(10**6)

def rec(x, c):
    if x <= 0:
        return 0
    if x in memo:
        return memo[x]
    if x % c == 0:
        memo[x] = min(rec(x // c, c) + 1, (x + c - 2) // (c - 1))
    else:
        memo[x] = min(rec(x - x % c, c) + 1, (x + c - 2) // (c - 1))
    return memo[x]

for _ in range(int(input())):
    a, b, c = map(int, input().split())
    if c == 1:
        print(-1)
    else:
        memo = dict()
        print(rec(a, c) * b)