题目描述

有一个无向图，顶点编号为 $1,2,\ldots,n$。若 $u\oplus v$ 是质数，则顶点 $u$ 和 $v$ 之间有一条边，其中 $\oplus$ 表示按位异或。

请用最少的颜色给所有顶点染色，使得任意一条边的两个端点颜色不同。你需要输出最少颜色数以及一种合法染色方案。

输入格式

第一行一个整数 $t$，表示测试组数。

每组数据一行一个整数 $n$。

输出格式

对每组数据输出两行。

第一行一个整数 $k$，表示最少需要的颜色数。

第二行 $n$ 个整数 $c_1,c_2,\ldots,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

说明

例如当 $n=2$ 时，顶点 $1$ 和 $2$ 之间有边，因为 $1\oplus2=3$ 是质数，所以至少需要 $2$ 种颜色。

数据范围

$1\le t\le500$，$1\le n\le2\times10^5$。

所有测试组的 $n$ 之和不超过 $2\times10^5$。