Q = int(input())
def main():
    A, B, C = map(int, input().split())
    n = 0
    while True:
        x = A //C
        y = A % C
        # print(A,x,y,"n",n)
        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()