Arseniy 决定让他的朋友 Dabir 和 Egor 开心。为此,他决定给他们每个人一组数字 相同长度。调用数组 $$$b$$$ 好 如果可以重新排列其元素,以便对于所有 $$$i \gt 1$$$ 条件 $$$b_i - b_{i - 1} = 1$$$ 成立。
Arseniy 希望 Dabir 和 Egor 能够使用这些阵列。为此,必须满足以下条件:
- 每个给定的数组是 好.
- 如果您在另一个数组之后写入一个数组(换句话说,将它们连接起来),则生成的数组也是 好.
Arseniy 已经有一个长度为 $$$n$$$ 的数组 $$$a$$$。他计划从$$$a$$$中切出两个数组,即选择两个不重叠的子段 相同长度。帮助阿尔森尼确定 最大 结果数组的可能长度。
输入
第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,输出一个整数 - 最大 数组的可能长度。
示例
输入复制
71121 232 1 142 1 4 351 2 4 5 363 2 1 6 5 4101 1 2 3 4 1 6 5 7 8
输出复制
0112134
注意
在第一个示例中,不可能选择 $$$2$$$ 数组,因此答案是 $$$0$$$。
在第二个示例中,所选数组的最大长度为 $$$1$$$。可以选择数组 [$$$1$$$] 和 [$$$2$$$]。
在第四个示例中,所选数组的最大长度为$$$2$$$。您可以选择数组 [$$$2, 1$$$] 和 [$$$4, 3$$$]。
在第五个示例中,所选数组的最大长度为$$$1$$$。选择数组的一种方法是 [$$$1$$$] 和 [$$$2$$$]。其他方法是数组 [$$$2$$$] 和 [$$$3$$$]、[$$$3$$$] 和 [$$$4$$$] 或 [$$$4$$$] 和 [$$$5$$$]。