← 返回题目列表

Codeforces · 1548/B

B. 整数有朋友

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

英国数学家约翰·利特伍德(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

输出 #1

3
3
2
6

注意

在第一个测试用例中,数组是$$$[1,5,2,4,6]$$$。最大的朋友组是 $$$[2,4,6]$$$,因为所有这些数字都与 $$$0$$$ 模 $$$2$$$ 一致,所以 $$$m=2$$$。

在第二个测试用例中,数组是$$$[8,2,5,10]$$$。最大的朋友组是 $$$[8,2,5]$$$,因为所有这些数字都与 $$$2$$$ 模 $$$3$$$ 一致,所以 $$$m=3$$$。

第三种情况,最大的朋友组是$$$[1000,2000]$$$。显然,$$$m$$$ 有许多可能的值。