CF2236E.Friendly Gifts

Arseniy decided to make his friends Dabir and Egor happy. For this, he decided to give each of them an array of numbers of the same length. An array $b$ is called good if its elements can be rearranged so that for all $i \gt 1$ the condition $b_i - b_{i - 1} = 1$ holds.

Arseniy wants Dabir and Egor to be able to play with these arrays. For this, the following conditions must be satisfied:

1. Each of the given arrays is good.
2. If you write one array after the other (in other words, concatenate them), the resulting array is also good.

Arseniy already has an array $a$ of length $n$. He plans to cut both arrays from $a$, that is, to choose two non-overlapping subsegments of the same length. Help Arseniy determine the maximum possible length of the resulting arrays.

阿尔塞尼决定让他的朋友达比尔和埃戈尔开心。为此，他决定分别送给他们一个长度相同的数字数组。若数组 $b$ 的元素可以重新排列，使得对所有 $i > 1$ 均满足 $b_i - b_{i-1} = 1$，则称该数组 $b$ 是“好的”。

阿尔塞尼希望达比尔和埃戈尔能用这些数组一起玩耍。为此，需满足以下条件：

1. 给定的两个数组各自都是“好的”；
2. 若将其中一个数组接在另一个数组之后（即二者拼接），所得的数组也必须是“好的”。

阿尔塞尼已有一个长度为 $n$ 的数组 $a$。他计划从 $a$ 中切出这两个数组，即选择两个长度相同且互不重叠的子段。请帮助阿尔塞尼确定所得数组的最大可能长度。

The first line contains a single integer $t$ $(1 \le t \le 1000)$ — the number of test cases.

Then $t$ test cases follow.

The first line of each test case contains a single integer $n$ $(1 \le n \le 6000)$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ $(1 \le a_i \le n)$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $6000$.

第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 表示测试用例的数量。

接下来是 $t$ 个测试用例。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 6000$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$）。

保证所有测试用例的 $n$ 值之和不超过 $6000$。

For each test case, output a single integer — the maximum possible length of the arrays.

对于每个测试用例，输出一个整数——数组可能的最大长度。

In the first sample, it is impossible to select $2$ arrays, so the answer is $0$.

In the second sample, the maximum length of the selected arrays is $1$. Arrays [$1$] and [$2$] can be selected.

In the fourth sample, the maximum length of the selected arrays is $2$. You can select arrays [$2, 1$] and [$4, 3$].

In the fifth sample, the maximum length of the selected arrays is $1$. One way to select arrays is [$1$] and [$2$]. Other methods are arrays [$2$] and [$3$], [$3$] and [$4$], or [$4$] and [$5$].

在第一个样例中，无法选择 $2$ 个数组，因此答案为 $0$。

在第二个样例中，所选数组的最大长度为 $1$。可以选择数组 [$1$] 和 [$2$]。

在第四个样例中，所选数组的最大长度为 $2$。可以选择数组 [$2, 1$] 和 [$4, 3$]。

在第五个样例中，所选数组的最大长度为 $1$。一种选择数组的方式是 [$1$] 和 [$2$]。其他方式包括数组 [$2$] 和 [$3$]、[$3$] 和 [$4$]，或 [$4$] 和 [$5$]。