Strongly Composite
Contest: Codeforces Round 868 (Div. 2)
Difficulty rating: 1300
Tags: greedy, math, number theory

A prime number is an integer greater than $$$1$$$, which has exactly two divisors. For example, $$$7$$$ is a prime, since it has two divisors $$$\{1, 7\}$$$. A composite number is an integer greater than $$$1$$$, which has more than two different divisors.

Note that the integer $$$1$$$ is neither prime nor composite.

Let's look at some composite number $$$v$$$. It has several divisors: some divisors are prime, others are composite themselves. If the number of prime divisors of $$$v$$$ is less or equal to the number of composite divisors, let's name $$$v$$$ as strongly composite.

For example, number $$$12$$$ has $$$6$$$ divisors: $$$\{1, 2, 3, 4, 6, 12\}$$$, two divisors $$$2$$$ and $$$3$$$ are prime, while three divisors $$$4$$$, $$$6$$$ and $$$12$$$ are composite. So, $$$12$$$ is strongly composite. Other examples of strongly composite numbers are $$$4$$$, $$$8$$$, $$$9$$$, $$$16$$$ and so on.

On the other side, divisors of $$$15$$$ are $$$\{1, 3, 5, 15\}$$$: $$$3$$$ and $$$5$$$ are prime, $$$15$$$ is composite. So, $$$15$$$ is not a strongly composite. Other examples are: $$$2$$$, $$$3$$$, $$$5$$$, $$$6$$$, $$$7$$$, $$$10$$$ and so on.

You are given $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$a_i > 1$$$). You have to build an array $$$b_1, b_2, \dots, b_k$$$ such that following conditions are satisfied:

- Product of all elements of array $$$a$$$ is equal to product of all elements of array $$$b$$$: $$$a_1 \cdot a_2 \cdot \ldots \cdot a_n = b_1 \cdot b_2 \cdot \ldots \cdot b_k$$$;
- All elements of array $$$b$$$ are integers greater than $$$1$$$ and strongly composite;
- The size $$$k$$$ of array $$$b$$$ is the maximum possible.

Find the size $$$k$$$ of array $$$b$$$, or report, that there is no array $$$b$$$ satisfying the conditions.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the size of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integer $$$a_1, a_2, \dots a_n$$$ ($$$2 \le a_i \le 10^7$$$) — the array $$$a$$$ itself.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.

Output format:
For each test case, print the size $$$k$$$ of array $$$b$$$, or $$$0$$$, if there is no array $$$b$$$ satisfying the conditions.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, we can get array $$$b = [18]$$$: $$$a_1 \cdot a_2 = 18 = b_1$$$; $$$18$$$ is strongly composite number.

In the second test case, we can get array $$$b = [60]$$$: $$$a_1 \cdot a_2 \cdot a_3 = 60 = b_1$$$; $$$60$$$ is strongly composite number.

In the third test case, there is no array $$$b$$$ satisfying the conditions.

In the fourth test case, we can get array $$$b = [4, 105]$$$: $$$a_1 \cdot a_2 \cdot a_3 = 420 = b_1 \cdot b_2$$$; $$$4$$$ and $$$105$$$ are strongly composite numbers.

Example input:
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

Example output:
1
1
0
2
2
3
4
15

Editorial:
Let's understand criteria for a number $$$x$$$ being strongly composite. Let's factorize the number $$$x = {p_1}^{d_1} \cdot {p_2}^{d_2} \cdot \dots \cdot {p_m}^{d_m}$$$. The number of all divisors of $$$x$$$ is $$$D = \prod\limits_{i = 1}^{m} (d_i + 1)$$$.
Since the number of prime divisors is $$$m$$$, then the number of composite divisors of $$$x$$$ is $$$D - m - 1$$$. Then a number $$$x$$$ is strongly composite if $$$m \le D - m - 1$$$ or $$$2 \cdot m + 1 \le D$$$. Since $$$m$$$ is the number of $$$d_i + 1 \ge 2$$$, then $$$D \ge 2^m$$$.
Consider a weakened condition for a strongly composite number: $$$2 \cdot m + 1 \le 2^m$$$. If $$$m = 1$$$, then the condition is satisfied only if $$$d_1 \ge 2$$$. If $$$m = 2$$$, then the condition is satisfied only if $$$\max{(d_1, d_2)} \ge 2$$$. If $$$m \ge 3$$$, then the condition is always satisfied.
In summary, a number is not strongly composite if it is either a prime or the product of two distinct primes.
Now let's solve the problem. Let's split all numbers into primes. Assume we have pairs $$$(p_i, c_i)$$$, where $$$p_i$$$ is a prime number and $$$c_i$$$ is the number of its occurrences. We can take either two same prime numbers or three of any prime numbers.
The optimal strategy is to create the maximum number of pairs of same prime numbers $$$\sum\limits_i{\left\lfloor \frac{c_i}{2} \right\rfloor}$$$, and when there will be only $$$r = \sum\limits_i{(c_i \bmod 2)}$$$ different prime numbers remaining. We can merge these remaining primes in triples to get extra $$$\left\lfloor \frac{r}{3} \right\rfloor$$$ strongly composite numbers.
If, after merging triples, we have some primes left, we can add them to any already strongly composite number, and it won't change its total number.