← 返回题目列表

Codeforces · 1957/A

A. 斯蒂克冈

中文机器翻译题面 查看原题

你得到了 $$$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$$$ 的正方形。