PKU [3685]. Matrix.

Matrix

Time Limit: 6000MS	Memory Limit: 65536K
Total Submissions: 2290	Accepted: 415

Description

Given a N × N matrix A, whose element in the i - th row and j - th column A_{i j} 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

12

1 1

2 1

2 2

2 3

2 4

3 1

3 2

3 8

3 9

5 1

5 25

5 10

Sample Output

3
-99993
3
12
100007
-199987
-99993
100019
200013
-399969
400031
-99939

Source

POJ Founder Monthly Contest – 2008.08.31, windy7926778