Положительное целое число называется составным, если оно представимо в виде произведения двух положительных целых чисел, каждое из которых больше $$$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$$$.