我们称数组为 平衡 当且仅当其任何元素出现的次数相同。例如,$$$[1,1,3,3,6,6]$$$ 和 $$$[2,2,2,2]$$$ 是 平衡,但 $$$[1,2,3,3]$$$ 不是 平衡 (元素$$$1$$$和$$$3$$$出现的次数不同)。请注意,空数组始终是 平衡.
给定一个由 $$$n$$$ 整数组成的非递减数组 $$$a$$$。求最长的长度 平衡 子序列$$$^{\text{*}}$$$。
$$$^{\text{*}}$$$ 序列 $$$b$$$ 是序列 $$$a$$$ 的子序列,如果 $$$b$$$ 可以通过从任意位置删除几个(可能是零个或全部)元素从 $$$a$$$ 获得。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 100$$$) — $$$a$$$ 的长度。
第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_1\le a_2\le \cdots \le a_n\le n$$$) — $$$a$$$ 的元素。
输出
对于每个测试用例,输出一个整数 - 最长的长度 平衡 $$$a$$$ 的子序列。
示例
输入复制
451 1 4 4 421 2151 1 1 1 1 2 2 2 2 3 3 3 4 4 553 3 3 3 3
输出复制
4295
注意
在第一个测试用例中,整个数组 $$$a = [1, 1, 4, 4, 4]$$$ 不是 平衡 因为元素$$$1$$$出现的次数是$$$2$$$,而元素$$$4$$$出现的次数是$$$3$$$,它们不相等。子序列 $$$[1, 1, 4, 4]$$$ 是 平衡 因为元素$$$1$$$和$$$4$$$出现的次数都是$$$2$$$。因此,最长的长度 平衡 $$$a$$$ 的子序列是 $$$4$$$。
在第二个测试用例中,整个数组 $$$a = [1, 2]$$$ 已经 平衡,所以最长的长度 平衡 $$$a$$$ 的子序列是 $$$2$$$。
在第三个测试用例中,最长的 平衡 $$$a$$$ 的子序列是 $$$[1,1,1,2,2,2,3,3,3]$$$。
在第四个测试用例中,整个数组 $$$a = [3, 3, 3, 3, 3]$$$ 已经 平衡,所以最长的长度 平衡 $$$a$$$ 的子序列是 $$$5$$$。