CF1823C Strongly Composite

质数是指大于 $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$ 的整数，且都是强合数； - 数组 $b$ 的长度 $k$ 尽可能大。 请你求出数组 $b$ 的最大可能长度 $k$，如果不存在满足条件的数组 $b$，输出 $0$。

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

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

在第一个测试用例中，可以得到数组 $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$ 都是强合数。 由 ChatGPT 4.1 翻译