题目背景

此题为 Codeforces Round 868 (Div. 2) 的 C 题，直接去原网站提交即可。

点我跳转原题

1. 做完后记得选择这个选择题。 {{ select(1) }}

• 提交并且通过了
• 还没有提交，或者提交了 WA 了。

题目描述

质数是大于 $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$。

输入格式

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

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$ 是强合数。