PKU [3685]. Matrix.

Matrix

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

Description

N by N 행렬 A가 주어진다. 그 중 이 행렬의 i행 j열 성분인 A_{i j} 는 다음과 같은 방정식을 만족한다. :
i ² + 100000 × i + j ² - 100000 × j + i × j.   당신은 이 행렬에서 M번째로 작은 값을 찾아야 한다.

Input

첫번째 행의 입력은 테스트 케이스의 수이다.
각 테스트 케이스는 두 정수  N(1 ≤ N ≤ 50,000) 과 M(1 ≤ M ≤ N × N) 으로 구성되며, N과 M의 입력 이전엔 공백이 존재한다.

Output

각 테스트 케이스 별로 답을 찾아내서 한 줄에 출력하라.

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


크흠. 조금 늦어졌군요 -_-; 죄송합니다.

저번엔 좀 쉬운 문제들을 풀어봤으니 이번엔 조금 난이도 있는 문제를 풀어봅시다. ㅇ_ㅇ!
- 사실 좀 더러운 문제일지도? ㄱ- -