Integers Have Friends

题目描述

英国数学家 John Littlewood 曾经这样评价印度数学家 Srinivasa Ramanujan：“每一个正整数都是他的私人朋友。”

事实证明，正整数之间也可以成为朋友！给定一个由不同正整数组成的数组 $a$。

定义子数组 $a_i, a_{i+1}, \ldots, a_j$ 为一个“朋友团”，当且仅当存在一个整数 $m \ge 2$，使得 $a_i \bmod m = a_{i+1} \bmod m = \ldots = a_j \bmod m$，其中 $x \bmod y$ 表示 $x$ 除以 $y$ 的余数。

你的朋友 Gregor 想知道数组 $a$ 中最大的朋友团的大小。

输入格式

每组测试包含多组测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 2 \cdot 10^4$）。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示数组 $a$ 的长度。

接下来一行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^{18}$），表示数组 $a$ 的内容。保证 $a$ 中所有数字互不相同。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

输出共 $t$ 行，每行一个整数，表示数组 $a$ 中最大的朋友团的大小。

样例 #1

样例输入

4
5
1 5 2 4 6
4
8 2 5 10
2
1000 2000
8
465 55 3 54 234 12 45 78

样例输出

3
3
2
6

说明/提示

在第一个测试用例中，数组为 $[1,5,2,4,6]$。最大的朋友团是 $[2,4,6]$，因为这些数对 $2$ 取模都等于 $0$，即 $m=2$。

在第二个测试用例中，数组为 $[8,2,5,10]$。最大的朋友团是 $[8,2,5]$，因为这些数对 $3$ 取模都等于 $2$，即 $m=3$。

在第三个测试用例中，最大的朋友团是 $[1000,2000]$。显然有很多 $m$ 满足条件。

由 ChatGPT 4.1 翻译