CF1332B.Composite Coloring

A positive integer is called composite 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't: $1$, $2$, $3$, $17$, $97$.

Alice is given a sequence of $n$ composite numbers $a_1,a_2,\ldots,a_n$.

She wants to choose an integer $m \le 11$ and color each element one of $m$ colors from $1$ to $m$ so that:

• for each color from $1$ to $m$ there is at least one element of this color;
• each element is colored and colored exactly one color;
• 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) \gt 1$ for each pair $i, j$ if these elements are colored the same color.

Note that equal elements can be colored different colors — you just have to choose one of $m$ colors for each of the indices from $1$ to $n$.

Alice showed already that if all $a_i \le 1000$ then she can always solve the task by choosing some $m \le 11$.

Help Alice to find the required coloring. Note that you don't have to minimize or maximize the number of colors, you just have to find the solution with some $m$ from $1$ to $11$.

如果一个正整数可以表示为两个均大于 $1$ 的正整数的乘积，则称其为合数。例如，以下数字是合数：$6$、$4$、$120$、$27$；而以下数字不是合数：$1$、$2$、$3$、$17$、$97$。

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

她希望选择一个整数 $m \le 11$，并将序列中每个元素染上 $m$ 种颜色之一（颜色编号为 $1$ 至 $m$），使得满足以下条件：

• 对于每种颜色 $1$ 至 $m$，至少有一个元素被染成该颜色；
• 每个元素都被染色，且恰好染一种颜色；
• 任意两个被染成相同颜色的元素的最大公约数大于 $1$，即：对任意下标对 $i, j$，若 $a_i$ 与 $a_j$ 被染成同一种颜色，则必有 $\gcd(a_i, a_j) > 1$。

注意：相等的元素可以染成不同颜色——你只需为下标 $1$ 至 $n$ 中的每个位置选定 $m$ 种颜色之一即可。

Alice 已经证明：只要所有 $a_i \le 1000$，那么总存在某个 $m \le 11$，使得该染色任务总有解。

请帮助 Alice 找到一种满足要求的染色方案。注意：你无需最小化或最大化所用颜色数，只需找到一种使用 $1$ 至 $11$ 中某个 $m$ 的可行解即可。

The 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.

The first line of the test case contains a single integer $n$ ($1 \le n \le 1000$) — the amount of numbers in a sequence $a$.

The second line of the test case contains $n$ composite integers $a_1,a_2,\ldots,a_n$ ($4 \le a_i \le 1000$).

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $10^4$.

第一行包含一个整数 $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$。

For 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't have to minimize or maximize the number of colors, you just have to find the solution with some $m$ from $1$ to $11$.

Remember 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$).

对每个测试用例，输出 $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 \le m \le 11$ 的解即可。

注意：颜色 $1$ 至 $m$ 中的每一种都至少需使用一次；任意两个同色元素不应互质（即它们的最大公约数应大于 $1$）。

In the first test case, $\gcd(6,10)=2$, $\gcd(6,15)=3$ and $\gcd(10,15)=5$. Therefore, it's valid to color all elements the same color. Note that there are other colorings which satisfy Alice's requirement in this test case.

In the second test case there is only one element of each color, so the coloring definitely satisfies Alice's requirement.

在第一个测试用例中，$\gcd(6,10)=2$，$\gcd(6,15)=3$，且 $\gcd(10,15)=5$。因此，将所有元素染成同一种颜色是合法的。注意，在该测试用例中，还存在其他满足 Alice 要求的染色方案。

在第二个测试用例中，每种颜色仅有一个元素，因此该染色方案一定满足 Alice 的要求。