Stickogon

## 题目描述 给定 $n$ 个木棍，第 $i$ 个长度为 $a_i$。 你需要保证： * 构成的任意多边形每一边由一根木棍构成。 * 没有木棍用于多个多边形的边。 求通过这些木棍同时能构造的**正**多边形数量。 注：不可以破坏木棍。 ## 输入格式 第一行一个整数 $t$，表示数据组数。 接下来对于每组数据，第一行一个整数 $n$。 接下来 $n$ 个整数，表示 $a_i$。 ## 输出格式 共 $t$ 行，每行一个整数，表示答案。 ## 提示 对于第一组数据，显然一根木棍无法构造多边形。 对于第二组数据，显然两根木棍也无法构造多边形。 对于第三组数据，可以用四根长度为 $3$ 的木棍构造一个正方形。 对于第四组数据，可以用五根长度为 $2$ 的木棍构造一个五边形，然后用四根长度为 $4$ 的木棍构造一个正方形。 ## 数据范围 对于全部数据，满足 $1\le t,n,a_i\le100$。

You are given $ n $ sticks of lengths $ a_1, a_2, \ldots, a_n $ . Find the maximum number of regular (equal-sided) polygons you can construct simultaneously, such that: - Each side of a polygon is formed by exactly one stick. - No stick is used in more than $ 1 $ polygon. Note: Sticks cannot be broken.

The first line contains a single integer $ t $ ( $ 1 \leq t \leq 100 $ ) — the number of test cases. The first line of each test case contains a single integer $ n $ ( $ 1 \leq n \leq 100 $ ) — the number of sticks available. The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq 100 $ ) — the stick lengths.

For each test case, output a single integer on a new line — the maximum number of regular (equal-sided) polygons you can make simultaneously from the sticks available.

4
1
1
2
1 1
6
2 2 3 3 3 3
9
4 2 2 2 2 4 2 4 4

0
0
1
2

In the first test case, we only have one stick, hence we can't form any polygon. In the second test case, the two sticks aren't enough to form a polygon either. In the third test case, we can use the $ 4 $ sticks of length $ 3 $ to create a square. In the fourth test case, we can make a pentagon with side length $ 2 $ , and a square of side length $ 4 $ .