import math
from collections import deque 



def main():

    n,k = map(int,input().split())

    
        

    curr = 1
    ans = -1

    while curr <= n:
        b = (curr - 1)//k * k + k
        step = b // k
        if b > n:
            ans = curr + (n - curr)//step * step
            break

        curr += (b - curr)//step * step


        
        front = curr + step
        rear = curr + step * k // (k-1) + 20 

        while front < rear:
            mid = (front + rear)//2
            should = (mid - 1)//k+1 
            actual = mid - curr
            if actual < should:
                front = mid + 1
            else:
                rear = mid 

        ans = curr

        curr = front
        
    print(ans)
 
        
               
    

        


 

        










T = int(input())
t = 1
while t <= T:
    main()
    t += 1