Q = int(input())
def main():
    A, B, C = map(int, input().split())
    if C == 1:
        print(-1)
    else:
        n = 0
        while True:
            x = A //C
            y = A % C
            if x == 0 and y == 0:
                break
            if x == 0:
                n += 1
                break
            # 割って2未満なら、2つ作ったほうがよい。
            elif x == 1:
                n += 2
                break
            elif y == 0:
                n += 1
            else:
                n += 2
            A = x
        print(n*B)

for i in range(Q):
    main()