CF1823C.Strongly Composite

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 \gt 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.

质数是指大于 $1$ 的整数，且恰好有两个正因数。例如，$7$ 是质数，因为它的正因数集合为 $\{1, 7\}$。合数是指大于 $1$ 的整数，且具有两个以上的不同正因数。

注意：整数 $1$ 既不是质数，也不是合数。

考虑某个合数 $v$。它有若干个正因数：其中一些是质数，另一些本身也是合数。若 $v$ 的质因数（即作为 $v$ 的正因数的质数）的个数小于或等于其合因数（即作为 $v$ 的正因数的合数）的个数，则称 $v$ 为强合数（strongly composite）。

例如，数 $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$ 的强合数；
• 数组 $b$ 的长度 $k$ 尽可能大。

请找出满足条件的最大可能的 $k$ 值；若不存在满足条件的数组 $b$，则报告无解。

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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

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

对于每个测试用例，输出数组 $b$ 的大小 $k$；如果不存在满足条件的数组 $b$，则输出 $0$。

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.

在第一个测试用例中，我们可以得到数组 $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$ 均为强合数。