CF1991D Prime XOR Coloring

给定一个无向图，该图有 $n$ 个顶点，编号从 $1$ 到 $n$。当且仅当 $u \oplus v$ 是一个质数时，顶点 $u$ 和顶点 $v$ 之间存在一条边，其中 $\oplus$ 表示按位异或运算。 请使用最少的颜色对图中的所有顶点进行染色，使得任意两个直接相连的顶点颜色不同。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 500$），表示测试数据的组数。 接下来每组测试数据包含一行，一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示图中顶点的数量。 保证所有测试数据中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每组测试数据，输出两行。 第一行输出一个整数 $k$（$1 \le k \le n$），表示所需的最小颜色数。 第二行输出 $n$ 个整数 $c_1, c_2, \ldots, c_n$（$1 \le c_i \le k$），表示每个顶点的颜色。 如果有多种方案，输出任意一种均可。

在第一个测试样例中，最小颜色数为 $1$，因为只有一个顶点。 在第二个测试样例中，最小颜色数为 $2$，因为 $1$ 和 $2$ 之间有一条边（$1 \oplus 2 = 3$，是质数）。 在第三个测试样例中，最小颜色数仍为 $2$，因为 $2$ 和 $3$ 可以染成相同的颜色，因为它们之间没有边（$2 \oplus 3 = 1$，不是质数）。 在第四个测试样例中，可以证明最小颜色数为 $3$。 在第五个测试样例中，可以证明最小颜色数为 $3$。 在第六个测试样例中，可以证明最小颜色数为 $4$。 由 ChatGPT 4.1 翻译