Положительное целое число называется составным, если оно представимо в виде произведения двух положительных целых чисел, каждое из которых больше \(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\).
Выходные данные
Для каждого набора входных данных выведите \(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\)).
Примечание
В первом наборе входных данных \(\gcd(6,10)=2\), \(\gcd(6,15)=3\) и \(\gcd(10,15)=5\). Таким образом, допустимо раскрасить все три элемента в один цвет. Обратите внимание, что для данного набора входных данных существуют и другие раскраски, которые удовлетворяют требованиям Алисы.
Во втором наборе входных данных в каждый цвет покрашен только один элемент, так что раскраска точно походит под все требования Алисы.
Примеры
| № | Входные данные | Выходные данные |
|
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
|