Kinich 醒来,新的一天开始了。他打开手机,查看邮箱,发现了一份神秘礼物。他决定打开礼物的盒子。
Kinich 用 $$$n$$$ 整数拆箱数组 $$$a$$$。最初,Kinich 的得分为 $$$0$$$。他将执行以下操作任意多次:
- 选择两个索引 $$$i$$$ 和 $$$j$$$ $$$(1 \leq i < j \leq n)$$$,使得在之前的任何操作中都没有选择 $$$i$$$ 和 $$$j$$$,并且 $$$a_i = a_j$$$。然后,将 $$$1$$$ 添加到他的分数中。
输出 Kinich 在执行上述操作任意次数后可以获得的最大分数。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 500$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 20$$$) — $$$a$$$ 的长度。
每个测试用例的以下行包含 $$$n$$$ 空格分隔的整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$)。
输出
对于每个测试用例,在新行中输出可达到的最高分数。
示例
输入 #1
5 1 1 2 2 2 2 1 2 4 1 2 3 1 6 1 2 3 1 2 3
输出 #1
0 1 0 1 3
注意
在第一个和第三个测试用例中,Kinich 无法执行任何操作。
在第二个测试用例中,Kinich 可以使用 $$$i=1$$$ 和 $$$j=2$$$ 执行一项操作。
在第四个测试用例中,Kinich 可以使用 $$$i=1$$$ 和 $$$j=4$$$ 执行一项操作。