← 返回题目列表

Codeforces · 1823/C

C. 强复合

中文机器翻译题面 查看原题

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