Many Perfect Squares

题意翻译

有 $n$ 个数 $(1 \le n \le 50)$ 。 它们分别是 $a_1,a_2,...,a_n$ 。你需要选择一个数 $x$ ，使得 $x$ 在 $0$ 至 $10^{18}$ 之内，并且 $a_1 + x,a_2 + x,a_3 + x ... a_n +x$ 中有尽可能多的完全平方数。询问当 $x$ 最优时,有多少个数是完全平方数。

题目描述

You are given a set $ a_1, a_2, \ldots, a_n $ of distinct positive integers. We define the squareness of an integer $ x $ as the number of perfect squares among the numbers $ a_1 + x, a_2 + x, \ldots, a_n + x $ . Find the maximum squareness among all integers $ x $ between $ 0 $ and $ 10^{18} $ , inclusive. Perfect squares are integers of the form $ t^2 $ , where $ t $ is a non-negative integer. The smallest perfect squares are $ 0, 1, 4, 9, 16, \ldots $ .

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 50 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 50 $ ) — the size of the set. The second line contains $ n $ distinct integers $ a_1, a_2, \ldots, a_n $ in increasing order ( $ 1 \le a_1 < a_2 < \ldots < a_n \le 10^9 $ ) — the set itself. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 50 $ .

输出格式

For each test case, print a single integer — the largest possible number of perfect squares among $ a_1 + x, a_2 + x, \ldots, a_n + x $ , for some $ 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

说明

In the first test case, for $ x = 0 $ the set contains two perfect squares: $ 1 $ and $ 4 $ . It is impossible to obtain more than two perfect squares. In the second test case, for $ x = 3 $ the set looks like $ 4, 9, 16, 25, 100 $ , that is, all its elements are perfect squares.

题目大意：
给定一个由不同的正整数组成的集合 $ a_1, a_2, \ldots, a_n $。定义整数 $ x $ 的平方度为在 $ a_1 + x, a_2 + x, \ldots, a_n + x $ 之间完全平方数的数量。找出在 $ 0 $ 到 $ 10^{18} $ 之间所有整数 $ x $ 的最大平方度。

输入输出格式：
输入格式：
每个测试包含多个测试案例。第一行包含测试案例的数量 $ 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 $。

输出格式：
对于每个测试案例，打印一个整数——在 $ 0 \le x \le 10^{18} $ 的范围内，$ a_1 + x, a_2 + x, \ldots, a_n + x $ 中可能的最大完全平方数的数量。

输入输出样例：
输入样例 #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 $，即，其所有元素都是完全平方数。题目大意： 给定一个由不同的正整数组成的集合 $ a_1, a_2, \ldots, a_n $。定义整数 $ x $ 的平方度为在 $ a_1 + x, a_2 + x, \ldots, a_n + x $ 之间完全平方数的数量。找出在 $ 0 $ 到 $ 10^{18} $ 之间所有整数 $ x $ 的最大平方度。 输入输出格式： 输入格式： 每个测试包含多个测试案例。第一行包含测试案例的数量 $ 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 $。 输出格式： 对于每个测试案例，打印一个整数——在 $ 0 \le x \le 10^{18} $ 的范围内，$ a_1 + x, a_2 + x, \ldots, a_n + x $ 中可能的最大完全平方数的数量。 输入输出样例： 输入样例 #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 $，即，其所有元素都是完全平方数。