CF1646A.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 \lt 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.

路易斯有一个由 $n+1$ 个整数组成的序列 $a_1, a_2, \ldots, a_{n+1}$。对每个 $i = 1, 2, \ldots, n+1$，保证满足 $0\leq a_i \lt n$ 或 $a_i=n^2$。他计算了该序列所有元素的和，并将该值记为 $s$。

路易斯丢失了他的序列，但他还记得 $n$ 和 $s$ 的值。你能找出该序列中等于 $n^2$ 的元素个数吗？

在给定约束条件下，答案是唯一的。

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 \lt 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.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 2\cdot 10^4$）。随后是测试用例的描述。

每个测试用例仅有一行，包含两个整数 $n$ 和 $s$（$1\le n \lt 10^6$，$0\le s \le 10^{18}$）。保证 $s$ 的值对于满足上述约束的某个序列是有效的和。

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

对于每个测试用例，输出一个整数——序列中等于 $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.

在第一个测试用例中，我们有 $s=0$，因此所有数字都等于 $0$，且序列中不存在等于 $49$ 的数字。

在第二个测试用例中，我们有 $s=1$。存在两种可能的序列：$[0, 1]$ 或 $[1, 0]$。在这两种情况下，数字 $1$ 均恰好出现一次。

在第三个测试用例中，我们有 $s=12$，这是本测试用例中 $s$ 的最大可能值。因此，数字 $4$ 在序列中出现了 $3$ 次。