Q = int(input())
for _ in range(Q):
    a, b, c = map(int, input().split())
    if c == 1:
        print(-1)
        continue
    cookie = a
    ans = 0
    while cookie > 0:
        if cookie < c:
            cookie = 0
        elif cookie % c == 0:
            cookie //= c
        elif (cookie - (cookie % c)) // c < cookie - (c - 1)*2:
            mod = cookie % c
            cookie -= mod
        else:
            cookie -= (c-1)
        ans += b

    print(ans)