def f(x, c):
    if c == 1:
        return -1
    if x == 0:
        return 0
    elif x < c:
        return 1
    elif x < 2*c - 1:
        return 2
    elif x%c != 0:
        return 1 + f(x - x%c, c)
    else:
        return 1 + f(x//c, c)

Q = int(input())

for _ in range(Q):
    a, b, c = map(int, input().split())
    
    res = f(a, c)
    if res > 0:
        res *= b
    print(res)