你得到了 $$$n$$$ 长度为 $$$a_1, a_2, \ldots, a_n$$$ 的棍子。找出可以同时构造的正多边形(等边)的最大数量,这样:
- 多边形的每一边都由一根棍子形成。
- 超过 $$$1$$$ 多边形中未使用任何棍子。
注意:木棍不能被折断。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 100$$$) — 可用的棍子数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 100$$$) - 棍子长度。
输出
对于每个测试用例,在新行中输出一个整数 - 您可以从可用的棍子上同时制作的规则(等边)多边形的最大数量。
示例
输入 #1
4 1 1 2 1 1 6 2 2 3 3 3 3 9 4 2 2 2 2 4 2 4 4
输出 #1
0 0 1 2
注意
在第一个测试用例中,我们只有一根棍子,因此我们无法形成任何多边形。
在第二个测试用例中,两根棍子也不足以形成多边形。
在第三个测试用例中,我们可以使用长度为 $$$3$$$ 的 $$$4$$$ 棍子来创建一个正方形。
在第四个测试用例中,我们可以制作一个边长为 $$$2$$$ 的五边形和一个边长为 $$$4$$$ 的正方形。