题目描述

给出正整数 $n$，请你确定一个正整数 $k$，并构造一个长度为 $n$ 的序列 $a$，其中每个数均为 $[1,k]$ 中的元素。

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

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

输入格式

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

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

输出格式

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

第二行包含 $n$ 个正整数，每个正整数均为 $[1,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

数据范围

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

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