The Peak Dilemma#13098
Mohammed has an array a_1,a_2,\ldots,a_n of integers where he picked his favorite integers from positive integers , If Mohammed has repeated a number more than once that explains that he loves it more than ones with appearing less time , However Mohanad decided to ruin the moment on purpose , He wanted Mohammed to improve his problem solving , so Mohanad has removed the whole array and told Mohammed only and that \sum\limits_{i=1}^n \sum\limits_{j=i}^n a_j=k originally , could you please determine the maximum possible value of a_n ?
The first line contains a single integer (1 \le t \le 10^4) – the number of test cases.
The only line of each test case contains two integers and (1 \le n \le 10^9 \, , \, 1 \le k \le 10^{18}).
It's guaranteed that at least one valid array exists.
For each test case, output a single integer – the maximum possible value of a_n.
Please note ! that the values won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).
Example 1
In the first test case , the array is , and \sum\limits_{i=1}^{1}\sum\limits_{j=i}^{1} a_j=a_1=5 , so a_1=5.
In the second test case , the array maximizes a_2 , we've
i=1 : 1+7=8.
i=2 : .
thus the sum is 8+7=15 , and a_2=8 is impossible since 8+8=16>15 already.
In the third test case , the array [3,1,3] maximizes a_3 , we've
i=1 : 3+1+3=7.
i=2 : 1+3=4.
i=3 : .
thus the sum is 7+4+3=14 , and a_3=4 is impossible since even [1,1,4] gives 6+5+4=15>14.
Subtask ( points) : (n=1)
Subtask ( points) : (\sum n \le 1000 \, , \, k \le 10^6)
Subtask ( points) : No additional constraints.