题目描述

Luis 有一个长度为 $n+1$ 的整数序列 $a_1, a_2, \ldots, a_{n+1}$。对于每个 $i=1,2,\ldots,n+1$，都保证 $0\leq a_i < n$，或者 $a_i = n^2$。他已经计算出了该序列所有元素的和，并将其记为 $s$。

现在 Luis 丢失了他的序列，但他还记得 $n$ 和 $s$ 的值。你能求出序列中等于 $n^2$ 的元素有多少个吗？

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

输入格式

每个测试点包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 2\cdot 10^4$），表示测试用例的数量。

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

输出格式

对于每个测试用例，输出一个整数，表示序列中等于 $n^2$ 的元素个数。

说明/提示

在第一个测试用例中，$s=0$，所以所有数字都等于 $0$，没有任何数字等于 $49$。

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

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

由 ChatGPT 4.1 翻译

样例

4
7 0
1 1
2 12
3 12

0
1
3
1