#include <bits/stdc++.h>

using namespace std;

// int res;

int myceil(double nums)
{
    int ty = (int) nums;
    if (nums > ty)
    {
        return ty + 1;
    }
    return ty;
}

// void dfs(int numbs, int cnt)
// {
//     res = min(res, numbs);
//     if (cnt == 0) return ;
//     else
//     {
//         dfs(numbs - 1, cnt - 1);
//         dfs(myceil((double)numbs / 2), cnt - 1);
//         dfs(myceil(sqrt((double)numbs)), cnt - 1);
//     }
// }

int main()
{
    int n;
    cin >> n;

    while (n -- )
    {
        int a, cnt;
        cin >> a >> cnt;
        while (cnt -- )
        {
//             cout << a << ' ';
            if (a <= 0)
            {
                cnt ++ ;
//                 cout << a << ' ' << cnt << endl;
                a = a - cnt;
                break;
            }
            int t = a - 1;
            t = min(myceil((double)a / 2), t);
//             cout << t << ' ';
            if (a >= 0) t = min(myceil(sqrt((double)a)), t);;

//             cout << t << ' ' << cnt << endl;
            a = t;
        }

        cout << a << endl;
    }

    return 0;
}