← 返回题目列表

Codeforces · 1332/B

B. 复合着色

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

如果一个正整数可以表示为两个都大于 $$$1$$$ 的两个正整数的乘积,则该正整数称为合数。例如,以下数字是合数:$$$6$$$、$$$4$$$、$$$120$$$、$$$27$$$。以下数字不是:$$$1$$$、$$$2$$$、$$$3$$$、$$$17$$$、$$$97$$$。

给 Alice 一个由 $$$n$$$ 复合数 $$$a_1,a_2,\ldots,a_n$$$ 组成的序列。

她想要选择一个整数 $$$m \le 11$$$ 并将每个元素着色为从 $$$1$$$ 到 $$$m$$$ 的 $$$m$$$ 颜色之一,以便:

- 对于从 $$$1$$$ 到 $$$m$$$ 的每种颜色,至少有一个该颜色的元素;
- 每个元素都有颜色,并且颜色恰好是一种颜色;
- 任何两个颜色相同的元素的最大公约数大于 $$$1$$$,即 $$$\gcd(a_i, a_j)>1$$$ 对于每对 $$$i, j$$$ 如果这些元素颜色相同。

请注意,相同的元素可以涂上不同的颜色 - 您只需为从 $$$1$$$ 到 $$$n$$$ 的每个索引选择 $$$m$$$ 颜色之一。

Alice 已经证明,如果所有 $$$a_i \le 1000$$$ 那么她总是可以通过选择一些 $$$m \le 11$$$ 来解决任务。

帮助爱丽丝找到所需的颜色。请注意,您不必最小化或最大化颜色数量,您只需找到具有从 $$$1$$$ 到 $$$11$$$ 的 $$$m$$$ 的解决方案即可。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。然后是测试用例的描述。

测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 1000$$$) — 序列 $$$a$$$ 中的数字数量。

测试用例的第二行包含 $$$n$$$ 复合整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$4 \le a_i \le 1000$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^4$$$。

输出

对于每个测试用例打印 $$$2$$$ 行。第一行应包含一个整数 $$$m$$$ ($$$1 \le m \le 11$$$) — 使用的颜色数量。考虑颜色的编号从 $$$1$$$ 到 $$$m$$$。第二行应包含满足上述条件的任何颜色。打印 $$$n$$$ 整数 $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le m$$$),其中 $$$c_i$$$ 是第 $$$i$$$ 个元素的颜色。如果有多个解决方案,那么您可以打印其中任何一个。请注意,您不必最小化或最大化颜色数量,您只需找到具有从 $$$1$$$ 到 $$$11$$$ 的 $$$m$$$ 的解决方案即可。

请记住,从 $$$1$$$ 到 $$$m$$$ 的每种颜色都应至少使用一次。任何两个相同颜色的元素不应互质(即它们的 GCD 应大于 $$$1$$$)。

示例

输入 #1

3
3
6 10 15
2
4 9
23
437 519 865 808 909 391 194 291 237 395 323 365 511 497 781 737 871 559 731 697 779 841 961

输出 #1

1
1 1 1
2
2 1
11
4 7 8 10 7 3 10 7 7 8 3 1 1 5 5 9 2 2 3 3 4 11 6

注意

在第一个测试用例中,$$$\gcd(6,10)=2$$$、$$$\gcd(6,15)=3$$$ 和 $$$\gcd(10,15)=5$$$。因此,将所有元素着色为相同颜色是有效的。请注意,在此测试用例中还有其他颜色可以满足 Alice 的要求。

在第二个测试用例中,每种颜色只有一个元素,因此着色绝对满足 Alice 的要求。