题解 | 小数字

'''
int()：向下取整，直接去掉小数部分。
math.floor()：向下取整，取小于或等于该数的最大整数。
math.ceil()：向上取整，取大于或等于该数的最小整数。
round()：四舍五入到最接近的整数。
math.trunc()：向零取整，直接去掉小数部分。
'''
from math import sqrt, ceil

while True:
    try:
        T = int(input())
        for _ in range(T):
            n, m = map(int,input().split())
            while m > 0:
                if n > 2:
                    n = ceil(sqrt(n))
                    m -= 1
                else:
                    n = n -m
                    m = 0
            print(n)
    except:
        break