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<cmath>

#include<cstdio>

#include<cctype>

#include<vector>

#include<cstring>

#include<iostream>

#include<algorithm>

#define lson ch[x][0]

#define rson ch[x][1]

#define hi puts("hi!");

#define int long long

using namespace std;

int n,m;

int get(int ith,int jth)

{

    return ith*ith+100000ll*ith-100000ll*jth+jth*jth+ith*jth;

}

int find(int x,int jth)

{

    int l=,r=n,mid;

    while(l<=r)

    {

        mid=(l+r)>>;

        if(get(mid,jth)<=x)

        {

            l=mid;

        }

        else

        {

            r=mid-;

        }

        if(r-l<=)

        {

            if(get(r,jth)<=x) mid=r;

            else mid=l;

            break;

        }

    }

    return mid;

}

int check(int x)

{

    int cnt=;

    for(int i=;i<=n;i++)

    {

        cnt+=find(x,i);

    }

    if(cnt>=m) return ;

    else return ;

}

signed main()

{

    int ttt;

    scanf("%lld",&ttt);

    while(ttt--)

    {

        int ans;

        scanf("%lld%lld",&n,&m);

        int l=-1e12,r=1e12,mid;

        while(l<=r)

        {

            mid=(l+r)>>;

            if(check(mid))

            {

                ans=mid;

                r=mid-;

            }

            else

            {

                l=mid+;

            }

        }

        printf("%lld\n",ans);

    }

}