import sys
#input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

for _ in range(int(input())):
    a, b, c = inpl()
    if c == 1:
        print(a*b)
        continue

    Q = []
    d = c - 1
    hoge = -(-a//(c-1))
    ans = 0

#    print(a, end = " ")

    while a:
        a, m = divmod(a, c)
        Q.append(m)
    
   # print(Q, end = " ")

    if (len(Q) >= 2) and (Q[-1] == 1) and (1 <= Q[-2] <= c-2):
        ans += 3
        Q.pop()
        Q.pop()
    
    while Q:
        x = Q.pop()
        ans += 1 + (x > 0)
    
    print(b*min(ans-1, hoge))