D. Карусель, карусель — это радость для нас
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Круглая карусель состоит из $$$n$$$ фигур различных животных. Фигуры пронумерованы от $$$1$$$ до $$$n$$$ по ходу движения карусели. Таким образом, после $$$n$$$-й фигуры идёт фигура с номером $$$1$$$. Каждая фигура имеет вид — это животного этой фигуры (лошадка, тигр и др.). Вид животного $$$i$$$-й фигуры равен $$$t_i$$$.

Пример изображения карусели для $$$n=9$$$ и $$$t=[5, 5, 1, 15, 1, 5, 5, 1, 1]$$$.

Вы хотите покрасить каждую фигуру в один из цветов. Вам кажется скучным, если в каруселе разные фигуры (с разными видами животных) идут подряд и покрашены в одинаковые цвета.

Ваша задача — покрасить фигуры так, чтобы количество различных использованных цветов было минимальным и не существовало двух фигур разного вида, которые идут подряд и покрашены в один цвет одновременно. Если Вы используете ровно $$$k$$$ различных цветов, то цвета фигур должны быть пронумерованы целыми числами от $$$1$$$ до $$$k$$$.

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

Входные данные состоят из одного или более набора входных данных.

В первой строке записано целое число $$$q$$$ ($$$1 \le q \le 10^4$$$) — количество наборов входных данных в тесте. Далее следуют описания $$$q$$$ наборов входных данных, по две строки на каждый набор.

Первая строка набора входных данных содержит одно целое число $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — количество фигур на карусели. Фигуры пронумерованы от $$$1$$$ до $$$n$$$ по ходу вращения карусели. Считайте, что после фигуры $$$n$$$ идёт фигура $$$1$$$.

Вторая строка набора входных данных содержит $$$n$$$ целых чисел $$$t_1, t_2, \dots, t_n$$$ ($$$1 \le t_i \le 2 \cdot 10^5$$$), где $$$t_i$$$ равно виду животного $$$i$$$-й фигуры.

Сумма значений $$$n$$$ по всем наборам входных данных в тесте не превосходит $$$2\cdot10^5$$$.

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

Выведите $$$q$$$ ответов — на для каждого набора входных данных выведите две строки.

В первую строку выведите одно целое число $$$k$$$ — минимально возможное количество различных цветов фигур.

Во вторую строку выведите $$$n$$$ целых чисел $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le k$$$), где $$$c_i$$$ обозначает номер цвета $$$i$$$-й фигуры. Если существует несколько возможных ответов, вы можете вывести любой из них.

Пример
Входные данные
4
5
1 2 1 2 2
6
1 2 2 1 2 2
5
1 2 1 2 3
3
10 10 10
Выходные данные
2
1 2 1 2 2
2
2 1 2 1 2 1
3
2 3 2 3 1
1
1 1 1