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 = []
    ans = 0
    
    while a:
        a, m = divmod(a, c)
        Q.append(m)
    
#    print(Q[::-1], 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(ans-1)