Given a N × N matrix A, whose element in the i-th row and j-th column A_ij is an number that equals i² + 100000 × i + j² - 100000 × j + i × j, you are to find the M-th smallest element in the matrix.

The first line of input is the number of test case.
For each test case there is only one line contains two integers, N(1 ≤ N ≤ 50,000) and M(1 ≤ M ≤ N × N). There is a blank line before each test case.

For each test case output the answer on a single line.

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int t;

long long n,k;

long long make(long long i,long long j){

    return i*i+j*j+i*-j*+i*j;

}

bool erfen(long long m){

    long long cnt=;

    for(int j=;j<=n;j++){

        int l=,r=n,ans=;

        while(l<=r){//内层二分

            int i=l+r>>;

            if(make(i,j)<=m){

                ans=i;

                l=i+;

            }

            else r=i-;

        }

        cnt+=ans;

    }

    return cnt>=k;

}

int main(){

    cin>>t;

    for(int w=;w<t;w++){

        cin>>n>>k;

        long long l=-*n;

        long long r=n*n+n*n+*n+n*n,ans;

        while(l<=r){//外层二分

            long long m=l+r>>;

            if(erfen(m)){

                ans=m;

                r=m-;

            }else l=m+;

        }

        cout<<ans<<endl;

    }

    return ;

}