def test():
    a, b, c = map(int, input().split())
    if c == 1:
        return -1
    n = 0
    while a:
        if a < c:
            n += 1
            break
        if a <= 2 * (c - 1):
            n += 2
            break
        if a % c == 0:
            n += 1
        else:
            n += 2
        a //= c
    return n * b


Q = int(input())
for _ in range(Q):
    print(test())