import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    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 < c:
                cnt += 1
                break
            if a <= 2 * (c - 1):
                cnt += 2
                break
            if a % c:
                cnt += 2
            else:
                cnt += 1
            a //= c
        print(cnt * b)

main()