import sys

def solve():
    input = sys.stdin.read().split()
    idx = 0
    Q = int(input[idx])
    idx += 1
    for _ in range(Q):
        A = int(input[idx])
        B = int(input[idx+1])
        C = int(input[idx+2])
        idx +=3
        
        if C ==1:
            if A ==0:
                print(0)
            else:
                print(-1)
            continue
        
        if A ==0:
            print(0)
            continue
        
        # Compute max_k
        max_k_val = 0
        current = 1
        while True:
            next_val = current * C
            if next_val > A:
                break
            current = next_val
            max_k_val +=1
        
        min_cost = float('inf')
        
        for current_k in range(0, max_k_val +1):
            remaining = A
            cost =0
            valid = True
            for i in range(current_k +1):
                power = current_k -i
                base = C ** power
                s_i = remaining // base
                remaining -= s_i * base
                if i ==0:
                    if s_i <1:
                        valid = False
                        break
                # Calculate cost_i
                if s_i ==0:
                    cost_i =0
                else:
                    cost_i = (s_i + C-2) // (C-1)  # ceiling(s_i / (C-1))
                cost += cost_i
            if valid and remaining ==0:
                total = (cost + current_k) * B
                if total < min_cost:
                    min_cost = total
        
        if min_cost != float('inf'):
            print(min_cost)
        else:
            print(-1)

if __name__ == '__main__':
    solve()