{"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\u003eA positive integer is called \u003cspan class\u003d\"tex-font-style-it\"\u003ecomposite\u003c/span\u003e if it can be represented as a product of two positive integers, both greater than $$$1$$$. For example, the following numbers are composite: $$$6$$$, $$$4$$$, $$$120$$$, $$$27$$$. The following numbers aren\u0027t: $$$1$$$, $$$2$$$, $$$3$$$, $$$17$$$, $$$97$$$.\u003c/p\u003e\u003cp\u003eAlice is given a sequence of $$$n$$$ composite numbers $$$a_1,a_2,\\ldots,a_n$$$.\u003c/p\u003e\u003cp\u003eShe wants to choose an integer $$$m \\le 11$$$ and color each element one of $$$m$$$ colors from $$$1$$$ to $$$m$$$ so that:\u003c/p\u003e\u003cul\u003e \u003cli\u003e for each color from $$$1$$$ to $$$m$$$ there is at least one element of this color; \u003c/li\u003e\u003cli\u003e each element is colored and colored exactly one color; \u003c/li\u003e\u003cli\u003e the greatest common divisor of any two elements that are colored the same color is greater than $$$1$$$, i.e. $$$\\gcd(a_i, a_j)\u0026gt;1$$$ for each pair $$$i, j$$$ if these elements are colored the same color. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eNote that equal elements can be colored different colors\u0026nbsp;— you just have to choose one of $$$m$$$ colors for each of the indices from $$$1$$$ to $$$n$$$.\u003c/p\u003e\u003cp\u003eAlice showed already that if all $$$a_i \\le 1000$$$ then she can always solve the task by choosing some $$$m \\le 11$$$.\u003c/p\u003e\u003cp\u003eHelp Alice to find the required coloring. Note that you don\u0027t have to minimize or maximize the number of colors, you just have to find the solution with some $$$m$$$ from $$$1$$$ to $$$11$$$.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains a single integer $$$t$$$ ($$$1 \\le t \\le 1000$$$) — the number of test cases. Then the descriptions of the test cases follow.\u003c/p\u003e\u003cp\u003eThe first line of the test case contains a single integer $$$n$$$ ($$$1 \\le n \\le 1000$$$) — the amount of numbers in a sequence $$$a$$$.\u003c/p\u003e\u003cp\u003eThe second line of the test case contains $$$n$$$ composite integers $$$a_1,a_2,\\ldots,a_n$$$ ($$$4 \\le a_i \\le 1000$$$).\u003c/p\u003e\u003cp\u003eIt is guaranteed that the sum of $$$n$$$ over all test cases doesn\u0027t exceed $$$10^4$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case print $$$2$$$ lines. The first line should contain a single integer $$$m$$$ ($$$1 \\le m \\le 11$$$) — the number of used colors. Consider colors to be numbered from $$$1$$$ to $$$m$$$. The second line should contain any coloring that satisfies the above conditions. Print $$$n$$$ integers $$$c_1, c_2, \\dots, c_n$$$ ($$$1 \\le c_i \\le m$$$), where $$$c_i$$$ is the color of the $$$i$$$-th element. If there are multiple solutions then you can print any of them. Note that you don\u0027t have to minimize or maximize the number of colors, you just have to find the solution with some $$$m$$$ from $$$1$$$ to $$$11$$$.\u003c/p\u003e\u003cp\u003eRemember that each color from $$$1$$$ to $$$m$$$ should be used at least once. Any two elements of the same color should not be coprime (i.e. their GCD should be greater than $$$1$$$).\u003c/p\u003e"}},{"title":"Examples","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\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first test case, $$$\\gcd(6,10)\u003d2$$$, $$$\\gcd(6,15)\u003d3$$$ and $$$\\gcd(10,15)\u003d5$$$. Therefore, it\u0027s valid to color all elements the same color. Note that there are other colorings which satisfy Alice\u0027s requirement in this test case.\u003c/p\u003e\u003cp\u003eIn the second test case there is only one element of each color, so the coloring definitely satisfies Alice\u0027s requirement.\u003c/p\u003e"}}]}