{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e如果一个正整数可以表示为两个大于$$$1$$$的正整数的乘积,则称其为\u003cspan class\u003d\"tex-font-style-it\"\u003e合数\u003c/span\u003e。例如,以下数字是合数:$$$6$$$、$$$4$$$、$$$120$$$、$$$27$$$。以下数字不是合数:$$$1$$$、$$$2$$$、$$$3$$$、$$$17$$$、$$$97$$$。\u003c/p\u003e\u003cp\u003e爱丽丝得到了一个由$$$n$$$个合数$$$a_1,a_2,\\ldots,a_n$$$组成的序列。\u003c/p\u003e\u003cp\u003e她想要选择一个整数$$$m \\le 11$$$,并将每个元素涂上从$$$1$$$到$$$m$$$共$$$m$$$种颜色之一,使得:\u003c/p\u003e\u003cul\u003e\u003cli\u003e对于每种颜色从$$$1$$$到$$$m$$$至少有一个元素;\u003c/li\u003e\u003cli\u003e每个元素被涂上且仅被涂上一种颜色;\u003c/li\u003e\u003cli\u003e任意两个被涂上相同颜色的元素的最大公约数大于$$$1$$$,即对于每一对$$$i, j$$$如果这些元素被涂上相同颜色。\u003c/li\u003e\u003c/ul\u003e\u003cp\u003e注意相同的元素可以被涂上不同的颜色 —— 你只需要为$$$1$$$到$$$n$$$之间的每个索引选择$$$m$$$种颜色中的一种。\u003c/p\u003e\u003cp\u003e爱丽丝已经证明了如果所有的$$$a_i \\le 1000$$$,那么她总是可以通过选择一些$$$m \\le 11$$$来解决这个问题。\u003c/p\u003e\u003cp\u003e帮助爱丽丝找到所需的涂色方案。注意,你不需要最小化或最大化颜色的数量,你只需要找到一种在从$$$1$$$到$$$11$$$中的某种$$$m$$$的解决方案。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e第一行包含一个整数$$$t$$$ ($$$1 \\le t \\le 1000$$$) —— 测试用例的数量。接下来是测试用例的描述。\u003c/p\u003e\u003cp\u003e测试用例的第一行包含一个整数$$$n$$$ ($$$1 \\le n \\le 1000$$$) —— 序列$$$a$$$中数字的数量。\u003c/p\u003e\u003cp\u003e测试用例的第二行包含$$$n$$$个合数$$$a_1,a_2,\\ldots,a_n$$$ ($$$4 \\le a_i \\le 1000$$$)。\u003c/p\u003e\u003cp\u003e保证所有测试用例中$$$n$$$的总和不超过$$$10^4$$$。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e对于每个测试用例,打印$$$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$$$的解决方案。\u003c/p\u003e\u003cp\u003e记住,每种颜色从$$$1$$$到$$$m$$$都应至少使用一次。任意两个相同颜色的元素不应互质(即它们的最大公约数应大于$$$1$$$)。\u003c/p\u003e"}},{"title":"示例1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n3\n6 10 15\n2\n4 9\n23\n437 519 865 808 909 391 194 291 237 395 323 365 511 497 781 737 871 559 731 697 779 841 961\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n1 1 1\n2\n2 1\n11\n4 7 8 10 7 3 10 7 7 8 3 1 1 5 5 9 2 2 3 3 4 11 6\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e在第一个测试用例中,$$$\\gcd(6,10)\u003d2$$$、$$$\\gcd(6,15)\u003d3$$$和$$$\\gcd(10,15)\u003d5$$$。因此,将所有元素涂成相同颜色是有效的。注意在这个测试用例中还有其他满足爱丽丝要求的涂色方案。\u003c/p\u003e\u003cp\u003e在第二个测试用例中,每种颜色只有一个元素,因此涂色肯定满足爱丽丝的要求。\u003c/p\u003e"}}]}