import math

def find_last_ans(n, k):
    if k > n / 2:
        return n
    c = k - 1
    ans = 1
    last_ans = 1
    while ans <= n:
        m = math.ceil(ans / c)
        next_multiple = math.ceil(ans / c) * c
        s = min((next_multiple - ans - 1) // m + 1, (n - ans) // m)
        if s <= 0:
            if ans + m <= n:
                ans += m
                last_ans = ans
            else:
                break
        else:
            ans += s * m
            last_ans = ans
    return last_ans

t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    print(find_last_ans(n, k))

answer.code:1:1: error: ‘import’ does not name a type
    1 | import math
      | ^~~~~~
answer.code:1:1: note: C++20 ‘import’ only available with ‘-fmodules-ts’, which is not yet enabled with ‘-std=c++20’