Q = int(input())
for i in range(Q):
    A, B, C = map(int, input().split())
    if C == 1:
        print(A*B)
        continue
    cnt = 0
    while True:
        if A <= 2*C:
            cnt += 2
            break
        A, b = A//C, A%C
        if A > 0:
            cnt += 1
        if b > 0:
            cnt += 1
        if A == 0:
            break
    print(B*cnt)