#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t --) {
        int n, m;
        cin >> n >> m;
        while (m --) {
            if (n >= 4) n = ceil(sqrt(n));
            else {
                n -= (m + 1);
                break;
            }
        }
        cout << n << '\n';
    }

    return 0;
}
// 64 位输出请用 printf("%lld")

n >= 4时 sqrt下降的比/2块

n < 4时 -1一定是最优处理之一,就统一-1了