← 返回题目列表

Codeforces · 1781/D

D. 许多完全平方数

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

给你一组 $$$a_1, a_2, \ldots, a_n$$$ 不同的正整数。

我们将整数 $$$x$$$ 的平方度定义为数字 $$$a_1 + x, a_2 + x, \ldots, a_n + x$$$ 中的完全平方数。

求 $$$0$$$ 和 $$$10^{18}$$$(含)之间所有整数 $$$x$$$ 的最大方形度。

完全平方数是 $$$t^2$$$ 形式的整数,其中 $$$t$$$ 是非负整数。最小的完全平方数是 $$$0, 1, 4, 9, 16, \ldots$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 50$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 50$$$) — 集合的大小。

第二行包含 $$$n$$$ 不同的整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_1 < a_2 < \ldots < a_n \le 10^9$$$) - 集合本身。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$50$$$。

输出

对于每个测试用例,打印一个整数 - $$$a_1 + x、a_2 + x、\ldots、a_n + x$$$ 中完美平方的最大可能数量,对于某些 $$$0 \le x \le 10^{18}$$$。

示例

输入 #1

4
5
1 2 3 4 5
5
1 6 13 22 97
1
100
5
2 5 10 17 26

输出 #1

2
5
1
2

注意

在第一个测试用例中,对于 $$$x = 0$$$,该集合包含两个完全平方数:$$$1$$$ 和 $$$4$$$。不可能获得两个以上的完全平方数。

在第二个测试用例中,对于 $$$x = 3$$$,该集合看起来像 $$$4, 9, 16, 25, 100$$$,也就是说,它的所有元素都是完全平方数。