小娴给阿笙出了一种简单数学题，小娴给出数字 ，并规定三种操作： 若 为非负整数，开根号（向上取整），即 ； 对当前的数字 减 ，即 ； 对当前数字除以 （向上取整），即 ； 现在可以对数字 操作 次，小娴想让阿笙计算出操作 次之后 最小可以为多少。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：在一行上输入两个整数 代表初始数字、操作次数。

输出描述:

对于每一组测试数据，在单独的一行上输出一个整数，代表操作 次之后 最小可以为多少。