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

Простое число — это целое число большее $$$1$$$, которое имеет ровно два делителя. Например, число $$$7$$$ простое, так как имеет два делителя $$$\{1, 7\}$$$. Составное число — это целое число большее $$$1$$$, которое имеет более двух различных делителей.

Обратите внимание, что число $$$1$$$ не является ни простым, ни составным.

Рассмотрим составное число $$$v$$$. Оно имеет несколько делителей: некоторые делители простые, остальные сами составные. Если число простых делителей числа $$$v$$$ меньше или равно числу составных делителей, назовем число $$$v$$$ сильно составным.

Например, число $$$12$$$ имеет $$$6$$$ делителей: $$$\{1, 2, 3, 4, 6, 12\}$$$, два делителя $$$2$$$ и $$$3$$$ — простые, в то время как три делителя $$$4$$$, $$$6$$$ и $$$12$$$ — составные. Поэтому, число $$$12$$$ сильно составное. Другие примеры сильно составных чисел: $$$4$$$, $$$8$$$, $$$9$$$, $$$16$$$ и так далее.

С другой стороны, делители числа $$$15$$$ — это $$$\{1, 3, 5, 15\}$$$: $$$3$$$ и $$$5$$$ простые, $$$15$$$ составное. Поэтому, число $$$15$$$ не сильно составное. Другие примеры: $$$2$$$, $$$3$$$, $$$5$$$, $$$6$$$, $$$7$$$, $$$10$$$ и так далее.

Вам даны $$$n$$$ чисел $$$a_1, a_2, \dots, a_n$$$ ($$$a_i > 1$$$). Вам необходимо построить массив $$$b_1, b_2, \dots, b_k$$$ который удовлетворяет следующим условиям:

  • Произведение всех элементов массива $$$a$$$ равно произведению всех элементов массива $$$b$$$: $$$a_1 \cdot a_2 \cdot \ldots \cdot a_n = b_1 \cdot b_2 \cdot \ldots \cdot b_k$$$;
  • Все элементы массива $$$b$$$ целые больше $$$1$$$ и являются сильно составными;
  • Размер $$$k$$$ массива $$$b$$$ максимально возможный.

Найдите размер $$$k$$$ массива $$$b$$$, или сообщите, что нет массива $$$b$$$ удовлетворяющего условиям.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 1000$$$) — размер массива $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots a_n$$$ ($$$2 \le a_i \le 10^7$$$) — сам массив $$$a$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$1000$$$.

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

Для каждого набора входных данных выведите размер $$$k$$$ массива $$$b$$$, или $$$0$$$, если нет массива $$$b$$$ удовлетворяющего условиям.

Пример
Входные данные
8
2
3 6
3
3 4 5
2
2 3
3
3 10 14
2
25 30
1
1080
9
3 3 3 5 5 5 7 7 7
20
12 15 2 2 2 2 2 3 3 3 17 21 21 21 30 6 6 33 31 39
Выходные данные
1
1
0
2
2
3
4
15
Примечание

В первом набор мы можем получить массив $$$b = [18]$$$: $$$a_1 \cdot a_2 = 18 = b_1$$$; $$$18$$$ является сильно составным числом.

Во втором наборе мы можем получить массив $$$b = [60]$$$: $$$a_1 \cdot a_2 \cdot a_3 = 60 = b_1$$$; $$$60$$$ является сильно составным числом.

В третьем наборе нет массива $$$b$$$ удовлетворяющего условиям.

В четвертом наборе мы можем получить массив $$$b = [4, 105]$$$: $$$a_1 \cdot a_2 \cdot a_3 = 420 = b_1 \cdot b_2$$$; $$$4$$$ и $$$105$$$ являются сильно составными числами.