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>

using namespace std;

long long N, M;

const long long INF = 1LL << 50;

long long mtr ( long long  i, long long j )

{

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

}

bool b_s ( long long X )

{

	long long res = 0;

	for ( int i = 1; i <= N; i++ )

		{

			int cnt = N ;

			int l = 1, r = N;

			while ( l <= r )

				{

					int mid = ( r + l ) >> 1;

					if ( mtr ( mid, i ) >= X )

						{

							r = mid - 1;

							cnt = mid - 1;

						}

					else

						{

							l = mid + 1;

						}

				}

			res += cnt ;

		}

	return res >= M;

}

int main()

{

	int n;

	cin >> n ;

	while ( n-- )

		{

			cin >> N >> M;

			long long l = -INF, r = INF;

			long long ans=-1;

			while ( l <= r )

				{

					long long mid = ( r + l )>>1;

					if ( b_s ( mid ) )

						{

							r = mid - 1;

							ans = mid - 1;

						}

					else

						{

							l = mid + 1;

						}

				}

			cout <<ans << endl;

		}

	return 0;

}