题目描述

给定一个长度为 $n$ 的整数数组 $a_1, a_2, \ldots, a_n$。你可以执行下面的操作一次：

• 选择一个整数 $x$（可以为负数），对于每一个 $i$ $(1 \leq i \leq n)$，将 $a_i$ 变为 $a_i + x$。

例如，如果 $a = [1, 3, 4, 2]$，你选择 $x = 3$ 进行操作，则 $a$ 变为 $[4, 6, 7, 5]$。

请输出操作后，数组 $a$ 的 $\operatorname{MEX}(a)^{\ast}$ 的最大可能值。

$\ast$ $\operatorname{MEX}(a)$ 表示数组中未出现的最小非负整数。例如，$\operatorname{MEX}([1, 2, 0, 5]) = 3$，$\operatorname{MEX}([1, 2, 4, 9]) = 0$。

输入格式

输入的第一行为一个整数 $t$ $(1 \leq t \leq 1000)$，表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ $(1 \le n \le 3000)$，表示数组 $a$ 的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(-10^9 \le a_i \le 10^9)$，表示数组 $a$。

保证所有测试用例中 $n$ 之和不超过 $3000$。

输出格式

对于每个测试用例，输出执行一次操作后 $\operatorname{MEX}(a)$ 的最大可能值。

说明/提示

对于第一个测试用例，可以选择 $x = -4$，此时 $a = [0]$，$\operatorname{MEX}([0]) = 1$。

对于第二个测试用例，$\operatorname{MEX}$ 已经是 $4$，已是最大值，因此可以选择 $x = 0$ 不进行任何变化。

由 ChatGPT 5 翻译

样例

6
1
4
5
0 1 1 2 3
2
1 1
4
4 2 3 6
5
2 4 1 0 -1
6
-1 1 2 3 5 6

1
4
1
3
4
3