E. Расшифровка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Агент по имени Кефир расшифровывает послание, которое содержит только одно составное число $$$n$$$.

Сначала Кефир выписывает по кругу все делители числа $$$n$$$, большие $$$1$$$. Он может задать любой изначальный порядок чисел в кругу.

После этого за одно действие Кефир может выбрать любые два соседние числа в кругу и вставить между ними их наименьшее общее кратное. Он может выполнять такое действие сколько угодно раз.

Послание расшифровано, если любые два соседние числа в кругу не взаимно просты. Заметим, что при заданных ограничениях послание всегда можно расшифровать.

Найдите, за какое минимальное количество действий послание можно расшифровать и как для этого нужно изначально расставить по кругу делители.

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

В первой строке находится единственное целое число $$$t$$$ $$$(1 \le t \le 100)$$$ — количество наборов входных данных. Следующие $$$t$$$ строк содержат описания наборов входных данных.

В единственной строке каждого набора входных данных находится единственное целое составное число $$$n$$$ $$$(4 \le n \le 10^9)$$$  — число из послания.

Гарантируется, что суммарное количество делителей $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных в первой строке выведите изначальный порядок делителей, больших $$$1$$$, в кругу. Во второй строке выведите минимальное количество действий, необходимых для того, чтобы расшифровать послание.

Если существует несколько возможных порядков с минимальным количеством действий, выведите любой.

Пример
Входные данные
3
6
4
30
Выходные данные
2 3 6 
1
2 4 
0
2 30 6 3 15 5 10 
0
Примечание

В первом наборе входных данных у числа $$$6$$$ три делителя, больших $$$1$$$: $$$2, 3, 6$$$. В любом случае числа $$$2$$$ и $$$3$$$ будут стоять рядом в кругу, и поэтому между ними необходимо вставить их наименьшее общее кратное. После этого в кругу будут числа $$$2, 6, 3, 6$$$, и каждые два соседних числа будут не взаимно просты.

Во втором наборе входных данных у числа $$$4$$$ два делителя, больших $$$1$$$: $$$2, 4$$$, и они не взаимно просты, поэтому вставлять наименьшее общее кратное не нужно.

В третьем наборе входных данных все делители $$$30$$$, большие $$$1$$$, можно расставить в кругу так, чтобы любые два соседние числа не были взаимно просты.