← 返回题目列表

Codeforces · 1646/A

A. 平方计数

中文机器翻译题面 查看原题

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\les \le 10^{18}$$$)。保证$$$s$$$ 的值是满足上述约束的某个序列的有效和。

输出

对于每个测试用例,打印一个整数 - 序列中等于 $$$n^2$$$ 的元素数量。

示例

输入 #1

4
7 0
1 1
2 12
3 12

输出 #1

0
1
3
1

注意

在第一个测试用例中,我们有 $$$s=0$$$,因此所有数字都等于 $$$0$$$,并且没有任何数字等于 $$$49$$$。

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

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