Непростая покраска

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

Задана последовательность из n составных чисел a1,a2,…,an.

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

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

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

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

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

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

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

Вторая строка набора входных данных содержит n составных целых чисел a1,a2,…,an (4≤ai≤1000).

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

Выходные данные
Для каждого набора входных данных выведите 2 строки. В первую выведите m (1≤m≤11) — количество использованных цветов. Считайте, что цвета пронумерованы от 1 до m. Во вторую строку выведите любую раскраску элементов, которая удовлетворяет условиям выше. Выведите n целых чисел c1,c2,…,cn (1≤ci≤m), где ci — цвет 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. Таким образом, допустимо раскрасить все три элемента в один цвет. Обратите внимание, что для данного набора входных данных существуют и другие раскраски, которые удовлетворяют требованиям Алисы.

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

ПОМОГИТЕ ЗДЕЛАТЬ ПОЖАЛУЙСТА!

0