D. 质数异或染色

时间限制：2 秒
空间限制：256 MB

给定一个包含 $n$ 个顶点的无向图，顶点编号从 $1$ 到 $n$。顶点 $u$ 和 $v$ 之间有边当且仅当 $u \oplus v$ 是质数，其中 $\oplus$ 表示按位异或运算。

请你用最少的颜色给图的所有顶点染色，使得任意一条边连接的两个顶点颜色不同。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 500$）—— 测试数据的组数。

接下来 $t$ 行，每行包含一个整数 $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, \dots, c_n$（$1 \le c_i \le k$）—— 每个顶点的颜色。

如果有多组解，输出任意一组均可。

样例输入

6
1
2
3
4
5
6

样例输出

1
1
2
1 2
2
1 2 2
3
1 2 2 3
3
1 2 2 3 3
4
1 2 2 3 3 4

样例解释

• 第一组：只有 $1$ 个顶点，最少需要 $1$ 种颜色。
• 第二组：顶点 $1$ 和 $2$ 之间有边（$1 \oplus 2 = 3$，是质数），最少需要 $2$ 种颜色。
• 第三组：顶点 $2$ 和 $3$ 之间可以同色，因为 $2 \oplus 3 = 1$ 不是质数，最少颜色仍是 $2$。
• 第四组：可以证明最少需要 $3$ 种颜色。
• 第五组：最少需要 $3$ 种颜色。
• 第六组：可以证明最少需要 $4$ 种颜色。