题目描述

小 Z 有一个正整数 $n$，现在小 Z 想要确定一个正整数 $k$，并且构造一个长度为 $n$ 的序列 $a$，其中序列 $a$ 中的每个数均为 $[1,k]$ 中的元素。

要求给出的序列需要满足：如果 $i \oplus j$ 为质数，那么 $a_i \neq a_j$，其中 $\oplus$ 为异或运算。

请你最小化正整数 $k$，并构造序列 $a$。

输入格式

一行，一个正整数 $T$，表示数据组数。

之后每组数据，给定一个正整数 $n$。

输出格式

对于每组数据，输出两行。第一行包含一个整数，表示答案 $k$。

第二行包含 $n$ 个正整数，每个正整数均为 $[1,k]$ 中的某个值。如果有多种符合要求的答案序列，输出任意一种即可。

样例

输入数据 1

6
1
2
3
4
5
6

输出数据 1

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

说明/提示

数据范围

对于 $30\%$ 的数据，$1 \le n \le 10$。

对于 $100\%$ 的数据，$1 \le n \le 5000$，$1 \le T \le 10$。