有 $n$ 名新生未能加入任何社团，他们决定自己组建两个新社团。为了结交更多新朋友，他们希望得到一个极度“随机”的分配结果。

形式化地，第 $i$ 名新生的个性可以用一个正整数 $w_i$ 表示，两名新生 $A$ 和 $B$ 之间的相似度可以用 $w_A \oplus w_B$ 来衡量，其中 “$\oplus$” 表示按位异或运算。你的任务是将每名新生分配到社团 1 或社团 2，使得同一社团内两名新生之间的最小相似度最大化。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 10\,000$)，表示测试数据的组数。

对于每组数据，第一行包含一个整数 $n$ ($3 \le n \le 100\,000$)，表示新生的数量。

第二行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$ ($1 \le i \le n, 1 \le w_i \le 10^9$)，表示每名新生的个性。

保证所有测试数据的 $n$ 之和不超过 $200\,000$。

输出格式

对于每组数据，输出两行。第一行输出一个整数，表示你所求方案中同一社团内两名新生之间的最小相似度。第二行输出 $n$ 个数字，表示你的分配方案。如果第 $i$ 名新生被分配到第一个社团，则第 $i$ 个数字应为 ‘1’；如果第 $i$ 名新生被分配到第二个社团，则第 $i$ 个数字应为 ‘2’。

如果存在多种方案，输出其中任意一种即可。

样例

样例输入 1

2
3
1 2 3
3
5 5 5

样例输出 1

3
112
0
122