1
2
3
4
5
6
7
8
9
10
11
12
def Josephus(n, k):
    stk = []
    while n >= k:
        stk.append(n)
        n -= n / k
    ret = 0
    for i in range(2, n + 1): ret = (ret + k) % i
    while len(stk):
        n = stk.pop()
        ret = ret - n % k + (n if ret < n % k else (ret - n % k) / (k - 1))
    return ret
for i in range(int(raw_input())): print Josephus(*map(int, raw_input().split()))
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX