D. Простая XOR раскраска
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан неориентированный граф с $$$n$$$ вершинами, пронумерованными от $$$1$$$ до $$$n$$$. Между вершинами $$$u$$$ и $$$v$$$ существует ребро тогда и только тогда, когда $$$u \oplus v$$$ является простым числом, где $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.

Раскрасьте все вершины графа в минимальное количество цветов так, чтобы ни одна пара вершин, непосредственно соединенных ребром, не была покрашена в один цвет.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка содержит одно целое число $$$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, \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
Примечание

В первом наборе входных данных минимальное количество цветов равно $$$1$$$, потому что дана только одна вершина.

Во втором наборе входных данных минимальное количество цветов равно $$$2$$$, потому что существует ребро, соединяющее $$$1$$$ и $$$2$$$ ($$$1 \oplus 2 = 3$$$, что является простым числом).

В третьем наборе входных данных минимальное количество цветов по-прежнему равно $$$2$$$, потому что $$$2$$$ и $$$3$$$ могут быть окрашены одинаково, так как между $$$2$$$ и $$$3$$$ нет ребра ($$$2 \oplus 3 = 1$$$, что не является простым числом).

В четвертом наборе входных данных можно показать, что минимальное количество цветов равно $$$3$$$.

В пятом наборе входных данных можно показать, что минимальное количество цветов равно $$$3$$$.

В шестом наборе входных данных можно показать, что минимальное количество цветов равно $$$4$$$.