Alice 和 Bob 正在玩游戏。最初,有 $$$n$$$ 个蛋糕,第 $$$i$$$ 个蛋糕的美味值为 $$$a_i$$$。
Alice 和 Bob 轮流吃它们,Alice 首先开始:
- 轮到爱丽丝选择并吃掉任何剩余的蛋糕,其味道严格高于她之前吃过的任何蛋糕的最大味道。请注意,在第一回合,她可以选择任何蛋糕。
- 轮到鲍勃选择剩余的蛋糕并吃掉它。
当前玩家吃不到合适的蛋糕时游戏结束。令 $$$x$$$ 为爱丽丝吃的蛋糕数量。然后,Alice 想要最大化 $$$x$$$,而 Bob 想要最小化 $$$x$$$。
找出如果两个玩家都发挥最佳状态,爱丽丝会吃多少个蛋糕。
输入
每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 500$$$) - 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5000$$$) — 蛋糕的数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — 蛋糕的美味值。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5000$$$。
输出
对于每个测试用例,输出一个整数 - 如果两个玩家都发挥最佳状态,爱丽丝将吃的蛋糕数量。
示例
输入 #1
9 4 1 4 2 3 3 1 1 1 5 1 4 2 3 4 4 3 4 1 4 1 1 8 4 3 2 5 6 8 3 4 7 6 1 1 3 5 3 1 11 6 11 6 8 7 5 3 11 2 3 5 17 2 6 5 3 9 1 6 2 5 6 3 2 3 9 6 1 6
输出 #1
2 1 3 2 1 3 2 4 4
注意
在第一个测试用例中,一个可能的轮次顺序是:
1. Alice 吃了一块美味值为 $$$1$$$ 的蛋糕。剩下的蛋糕是$$$[4,2,3]$$$。
2. Bob 吃了一块美味值为 $$$2$$$ 的蛋糕。剩下的蛋糕是$$$[4, 3]$$$。
3. Alice 吃了一块味道为 $$$3$$$ 的蛋糕。剩下的蛋糕是$$$[4]$$$。
4. Bob 吃了一块美味值为 $$$4$$$ 的蛋糕。剩下的蛋糕是$$$[]$$$。
5. 由于没有剩下蛋糕,游戏结束。
在第二个测试用例中,一种可能的轮流顺序是:
1. Alice 吃了一块美味值为 $$$1$$$ 的蛋糕。剩下的蛋糕是$$$[1, 1]$$$。
2. Bob 吃了一块美味值为 $$$1$$$ 的蛋糕。剩下的蛋糕是$$$[1]$$$。
3. 由于 Alice 已经吃了一块美味值为 $$$1$$$ 的蛋糕,她无法进行回合,因此游戏结束。