/*    给定n，有n*n个数，有aij=i * i + m * i + j * j - m * j + i * j    n <= 50000    m <= 100000    求所有aij中第m大的数    还是二分答案，先根据生成的式子，求出最大的和最小的数字，然后二分答案，验证    我们发现，对于同列的数字，按照行数的增加，数字大小是递增的    根据这个性质，就很容易验证是否存在>=n*n-m+1个数字>=val了    看了题一下子就有想法了，结果却wa了一天...原因在于自作聪明地进行数学推论然后非要从同行中进行二分...最后才发现不满足递减性质...不过最后ac的时候还是很爽快的 */#include <cstdio>#include <iostream>#include <vector>#include <algorithm>#define range(i,a,b) for (long long i=a;i<=b;i++)using namespace std;typedef long long ll;const ll m = 1e5;ll n;ll M;inline ll Int(ll i,ll j){    return i * i + m * i + j * j - m * j + i * j;}//找到最小的i，满足>=valll findK(ll j,ll val){    ll l(1),r(n);    while(l+1<r)    {        int mid = (l+r)>>1;        if (Int(mid,j) >= val)            r = mid;        else            l = mid;    }    //返回>=val的数字的个数    if (Int(l,j) >= val)        return n-l+1;    if (Int(r,j) >= val)        return n-r+1;    return 0;}bool test(ll val){    ll ans(0);    //返回每一行的>=val的数量    range(c,1,n)    {        ans += findK(c,val);    }    return ans >= (ll)n*n - M+1;    //必须要有>=n*n-M+1的数量>=ans，ans才有可能是答案}int main(){    int t;    cin>>t;    range(c,1,t)    {        cin>>n>>M;        ll l(-n*m),r(n*n*3 + n*m);        while(l+1<r)        {            ll mid = (l+r)/2;            if (mid == 5101786214)            {                cout<<"";            }            if (test(mid))            {                l = mid;            }            else            {                r = mid;            }        }        if (test(r))        {            cout<<r<<endl;        }        if (test(l))        {            cout<<l<<endl;        }    }    return 0;}