题目描述

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

• 选择一个整数 $x$（可以为负数），并对所有 $1 \le i \le n$，令 $a_i=a_i+x$。

例如，若 $a=[1,3,4,2]$，选择 $x=3$ 后，数组变为 $[4,6,7,5]$。

输出操作后 $\operatorname{MEX}(a)$ 的最大可能值。

$\operatorname{MEX}(a)$ 定义为数组中没有出现的最小非负整数。例如，$\operatorname{MEX}([1,2,0,5])=3$，$\operatorname{MEX}([1,2,4,9])=0$。

输入格式

第一行一个整数 $t$，表示测试组数。

每组测试数据第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

保证所有测试数据的 $n$ 之和不超过 $3000$。

输出格式

对于每组测试数据，输出操作后 $\operatorname{MEX}(a)$ 的最大可能值。

样例

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

样例说明

第一组测试数据中，选择 $x=-4$ 后数组变为 $[0]$，MEX 为 $1$。

第二组测试数据中，MEX 已经为 $4$，这是可能的最大值，可以选择 $x=0$。

数据范围

• $1 \le t \le 1000$
• $1 \le n \le 3000$
• $-10^9 \le a_i \le 10^9$
• 所有测试数据的 $n$ 之和不超过 $3000$

来源

Codeforces Round 1074 (Div. 4), Problem C - Shifted MEX