{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\u003cp\u003eGiven a \u003ci\u003eN\u003c/i\u003e × \u003ci\u003eN\u003c/i\u003e matrix A, whose element in the \u003ci\u003ei\u003c/i\u003e-th row and \u003ci\u003ej\u003c/i\u003e-th column \u003ci\u003eA\u003csub\u003eij\u003c/sub\u003e\u003c/i\u003e is an number that equals \u003ci\u003ei\u003c/i\u003e\u003csup\u003e2\u003c/sup\u003e + 100000 × \u003ci\u003ei\u003c/i\u003e + \u003ci\u003ej\u003c/i\u003e\u003csup\u003e2\u003c/sup\u003e - 100000 × \u003ci\u003ej\u003c/i\u003e + \u003ci\u003ei\u003c/i\u003e × \u003ci\u003ej\u003c/i\u003e, you are to find the \u003ci\u003eM\u003c/i\u003e-th smallest element in the matrix. 所有n加起来小于100000\u003c/p\u003e\u003c/div\u003e\n"}},{"title":"Input","value":{"format":"MD","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\u003cp\u003eThe first line of input is the number of test case.\u003cbr\u003eFor each test case there is only one line contains two integers, \u003ci\u003eN\u003c/i\u003e(1 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 50,000) and \u003ci\u003eM\u003c/i\u003e(1 ≤ \u003ci\u003eM\u003c/i\u003e ≤ \u003ci\u003eN\u003c/i\u003e × \u003ci\u003eN\u003c/i\u003e). There is a blank line before each test case. \u003c/p\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"MD","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\u003cp\u003eFor each test case output the answer on a single line.\u003c/p\u003e\u003c/div\u003e"}}]}