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

int main() {
    int t;
    cin >> t; 
    while (t--) {
        int n, m;
        cin >> n >> m;
        while (n && m) {
            int t = n;
            int x = sqrt(t);
            if (x * x != t) x++;
            n = min({n, x, t - 1, (t + 1) / 2}), m--;
        }
        n -= m;
        cout << n << endl;
    }
}