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.

Input

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.

Output

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

Sample Input

121 12 12 22 32 43 13 23 83 95 15 255 10

Sample Output

3-99993312100007-199987-99993100019200013-399969400031-99939

 

#include
     
      #include
      
       #include
       
        using namespace std;int t;long long n,k;long long make(long long i,long long j){    return i*i+j*j+i*100000-j*100000+i*j;}bool erfen(long long m){    long long cnt=0;    for(int j=1;j<=n;j++){        int l=1,r=n,ans=0;        while(l<=r){
   //内层二分             int i=l+r>>1;            if(make(i,j)<=m){                ans=i;                l=i+1;            }            else r=i-1;        }        cnt+=ans;    }    return cnt>=k;}int main(){    cin>>t;    for(int w=0;w
        
         >n>>k;        long long l=-100000*n;        long long r=n*n+n*n+100000*n+n*n,ans;        while(l<=r){
   //外层二分             long long m=l+r>>1;            if(erfen(m)){                 ans=m;                r=m-1;            }else l=m+1;        }        cout<
         
          <