素数是大于 $$$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$$$。
示例
输入 #1
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 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$$$ 是强合数。