const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    // Write your code here
    /**
     * 在数字大于2的时候，统一使用开根号的方式是最小的。
     * 在数字小于等于2的时候，统一使用减1的方式是最小的。
     */
    let t = await readline()
    while(line = await readline()){
        let [n, m] = line.split(' ').map(Number);
        for (let i=0; i<m; i++) {
            if (n > 2) {
                n = Math.ceil(Math.sqrt(n))
            } else {
                n -= (m-i)
                break
            }
        }
        console.log(n)
    }
}()