A14938 | Square Counting

Luis has a sequence of $n+1$ integers $a_1, a_2, \ldots, a_{n+1}$ . For each $i = 1, 2, \ldots, n+1$ it is guaranteed that $0\leq a_i < n$ , or $a_i=n^2$ . He has calculated the sum of all the elements of the sequence, and called this value $s$ .

Luis has lost his sequence, but he remembers the values of $n$ and $s$ . Can you find the number of elements in the sequence that are equal to $n^2$ ?

We can show that the answer is unique under the given constraints.

Each test contains multiple test cases. The first line contains the number of test cases $t$ ( $1 \le t \le 2\cdot 10^4$ ). Description of the test cases follows.

The only line of each test case contains two integers $n$ and $s$ ( $1\le n< 10^6$ , $0\le s \le 10^{18}$ ). It is guaranteed that the value of $s$ is a valid sum for some sequence satisfying the above constraints.

For each test case, print one integer — the number of elements in the sequence which are equal to $n^2$ .