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$ .

In the first test case, we have $s=0$ so all numbers are equal to $0$ and there isn't any number equal to $49$ .

In the second test case, we have $s=1$ . There are two possible sequences: $[0, 1]$ or $[1, 0]$ . In both cases, the number $1$ appears just once.

In the third test case, we have $s=12$ , which is the maximum possible value of $s$ for this case. Thus, the number $4$ appears $3$ times in the sequence.