from math import ceil
num = int(input())
for i in range(num):
    n, m = map(int,input().split())
    k = 0
    for j in range(m):
        if n <= 2:
            n = n - 1
            k = m - 1 - j
            break
        else:
            n = ceil(n**0.5)
    print(n - k)