题目描述

Arseniy 决定让他的朋友们 Dabir 和 Egor 开心。为此，他打算给他们每人一个长度相同的数组。如果一个数组 $b$ 的元素可以重新排列，使得对所有 $i \gt 1$ 满足条件 $b_i - b_{i - 1} = 1$，则称该数组是好的。

Arseniy 希望 Dabir 和 Egor 能够玩这些数组。为此，必须满足以下条件：

1. 每个给出的数组都是好的。
2. 如果将两个数组依次拼接（即连接它们），得到的数组也是好的。

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

输入格式

第一行包含一个整数 $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$。

输出格式

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

样例

7
1
1
2
1 2
3
2 1 1
4
2 1 4 3
5
1 2 4 5 3
6
3 2 1 6 5 4
10
1 1 2 3 4 1 6 5 7 8

0
1
1
2
1
3
4

提示

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

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

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

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