Агент по имени Кефир расшифровывает послание, которое содержит только одно составное число \(n\).
Сначала Кефир выписывает по кругу все делители числа \(n\), большие \(1\). Он может задать любой изначальный порядок чисел в кругу.
После этого за одно действие Кефир может выбрать любые два соседние числа в кругу и вставить между ними их наименьшее общее кратное. Он может выполнять такое действие сколько угодно раз.
Послание расшифровано, если любые два соседние числа в кругу не взаимно просты. Заметим, что при заданных ограничениях послание всегда можно расшифровать.
Найдите, за какое минимальное количество действий послание можно расшифровать и как для этого нужно изначально расставить по кругу делители.
Выходные данные
Для каждого набора входных данных в первой строке выведите изначальный порядок делителей, больших \(1\), в кругу. Во второй строке выведите минимальное количество действий, необходимых для того, чтобы расшифровать послание.
Если существует несколько возможных порядков с минимальным количеством действий, выведите любой.
Примечание
В первом наборе входных данных у числа \(6\) три делителя, больших \(1\): \(2, 3, 6\). В любом случае числа \(2\) и \(3\) будут стоять рядом в кругу, и поэтому между ними необходимо вставить их наименьшее общее кратное. После этого в кругу будут числа \(2, 6, 3, 6\), и каждые два соседних числа будут не взаимно просты.
Во втором наборе входных данных у числа \(4\) два делителя, больших \(1\): \(2, 4\), и они не взаимно просты, поэтому вставлять наименьшее общее кратное не нужно.
В третьем наборе входных данных все делители \(30\), большие \(1\), можно расставить в кругу так, чтобы любые два соседние числа не были взаимно просты.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
6
4
30
|
2 3 6
1
2 4
0
2 30 6 3 15 5 10
0
|