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