1982B - Collatz Conjecture - CodeForces Solution

t = int(input())
for _ in range(t):
    x, y ,k = map(int, input().split())


    while k > 0:
        if(x == 1 ):
            x += k % (y - 1)
            k = 0
        if( (x // y + 1 ) * y - x > k):
            x+=k
            k = 0
        else:
            k = k - ((x // y + 1 ) * y - x)
            
            x = (x // y + 1 ) * y
            while x % y == 0 :
                x = x//y

    
    print(x)