B. Непростая покраска
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Положительное целое число называется составным, если оно представимо в виде произведения двух положительных целых чисел, каждое из которых больше $$$1$$$. Например, следующие числа составные: $$$6$$$, $$$4$$$, $$$120$$$, $$$27$$$. Следующие числа составными не являются: $$$1$$$, $$$2$$$, $$$3$$$, $$$17$$$, $$$97$$$.

Задана последовательность из $$$n$$$ составных чисел $$$a_1,a_2,\ldots,a_n$$$.

Алиса хочет выбрать любое целое число $$$m \le 11$$$ и покрасить каждый элемент в один из $$$m$$$ цветов от $$$1$$$ до $$$m$$$ так, что:

  • для каждого цвета от $$$1$$$ до $$$m$$$ существует хотя бы один элемент этого цвета;
  • каждый элемент покрашен и притом ровно в один цвет;
  • наибольший общий делитель любых двух одноцветных элементов больше $$$1$$$, то есть $$$\gcd(a_i, a_j)>1$$$ для любой пары индексов $$$i, j$$$, если эти элементы покрашены в одинаковый цвет.

Обратите внимание, что одинаковые элементы могут быть покрашены в разные цвета — просто для каждого индекса от $$$1$$$ до $$$n$$$ надо выбрать один из $$$m$$$ цветов.

Алиса уже показала, что если все $$$a_i \le 1000$$$, то она всегда может решить эту задачу, выбрав некоторое $$$m \le 11$$$.

Помогите Алисе найти требуемую покраску элементов. Обратите внимание, что вам не нужно минимизировать или максимизировать количество цветов, достаточно найти решения с любым $$$m$$$ от $$$1$$$ до $$$11$$$.

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

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

В первой строке набора записано целое число $$$n$$$ ($$$1 \le n \le 1000$$$) — количество чисел в последовательности $$$a$$$.

Вторая строка набора входных данных содержит $$$n$$$ составных целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$4 \le a_i \le 1000$$$).

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^4$$$.

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

Для каждого набора входных данных выведите $$$2$$$ строки. В первую выведите $$$m$$$ ($$$1 \le m \le 11$$$) — количество использованных цветов. Считайте, что цвета пронумерованы от $$$1$$$ до $$$m$$$. Во вторую строку выведите любую раскраску элементов, которая удовлетворяет условиям выше. Выведите $$$n$$$ целых чисел $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le m$$$), где $$$c_i$$$ — цвет $$$i$$$-го элемента. Если решений несколько, то выведите любое из них. Обратите внимание, что вам не нужно минимизировать или максимизировать количество цветов, достаточно найти решения с любым $$$m$$$ от $$$1$$$ до $$$11$$$.

Помните, что каждый цвет от $$$1$$$ до $$$m$$$ должен быть использован хотя бы раз. Любые два одноцветных элемента должны не быть взаимно просты (то есть их НОД должен быть больше $$$1$$$).

Пример
Входные данные
3
3
6 10 15
2
4 9
23
437 519 865 808 909 391 194 291 237 395 323 365 511 497 781 737 871 559 731 697 779 841 961
Выходные данные
1
1 1 1
2
2 1
11
4 7 8 10 7 3 10 7 7 8 3 1 1 5 5 9 2 2 3 3 4 11 6
Примечание

В первом наборе входных данных $$$\gcd(6,10)=2$$$, $$$\gcd(6,15)=3$$$ и $$$\gcd(10,15)=5$$$. Таким образом, допустимо раскрасить все три элемента в один цвет. Обратите внимание, что для данного набора входных данных существуют и другие раскраски, которые удовлетворяют требованиям Алисы.

Во втором наборе входных данных в каждый цвет покрашен только один элемент, так что раскраска точно походит под все требования Алисы.