A. Палкоугольник
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны $$$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$$$) — длины палочек.

Выходные данные

Для каждого набора входных данных выведите в отдельной строке одно целое число — максимальное количество правильных (равносторонних) многоугольников, которые вы можете сформировать одновременно из имеющихся палочек.

Пример
Входные данные
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
Примечание

В первом наборе входных данных есть только одна палочка, поэтому мы не можем сформировать ни одного многоугольника.

Во втором наборе входных данных двух палочек также недостаточно, чтобы сформировать многоугольник.

В третьем наборе входных данных мы можем использовать $$$4$$$ палочки длины $$$3$$$ для формирования квадрата.

В четвертом наборе входных данных мы можем сформировать пятиугольник со стороной длиной $$$2$$$ и квадрат со стороной длиной $$$4$$$.