D. Много точных квадратов
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано множество $$$a_1, a_2, \ldots, a_n$$$ из различных положительных целых чисел.

Назовем квадратностью целого числа $$$x$$$ количество точных квадратов среди чисел $$$a_1 + x, a_2 + x, \ldots, a_n + x$$$.

Найдите максимальную квадратность среди всех целых чисел $$$x$$$ от $$$0$$$ до $$$10^{18}$$$ включительно.

Напомним, что точными квадратами являются числа вида $$$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}$$$.

Пример
Входные данные
4
5
1 2 3 4 5
5
1 6 13 22 97
1
100
5
2 5 10 17 26
Выходные данные
2
5
1
2
Примечание

В первом наборе входных данных при $$$x = 0$$$ в множестве будут два точных квадрата — $$$1$$$ и $$$4$$$. Более двух точных квадратов получить нельзя.

Во втором наборе входных данных при $$$x = 3$$$ множество примет вид $$$4, 9, 16, 25, 100$$$, то есть все его элементы станут точными квадратами.