D. Число в последовательность
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задано целое число $$$n$$$ ($$$n > 1$$$).

Ваша задача — найти последовательность целых чисел $$$a_1, a_2, \ldots, a_k$$$ такую, что:

  • каждое $$$a_i$$$ строго больше $$$1$$$;
  • $$$a_1 \cdot a_2 \cdot \ldots \cdot a_k = n$$$ (то есть произведение этой последовательности равно $$$n$$$);
  • $$$a_{i + 1}$$$ делится на $$$a_i$$$ для всех $$$i$$$ от $$$1$$$ до $$$k-1$$$;
  • $$$k$$$ является максимально возможным (то есть длина этой последовательности является максимально возможной).

Если существует несколько таких последовательностей, любая из них считается подходящей. Можно доказать, что хотя бы одна корректная последовательность всегда существует для любого целого числа $$$n > 1$$$.

Вам необходимо ответить на $$$t$$$ независимых наборов тестовых данных.

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

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 5000$$$) — количество наборов тестовых данных. Затем следуют $$$t$$$ наборов тестовых данных.

Единственная строка набора тестовых данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 10^{10}$$$).

Гарантируется, что сумма $$$n$$$ не превосходит $$$10^{10}$$$ ($$$\sum n \le 10^{10}$$$).

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

Выведите ответ на каждый набор тестовых данных: в первой строке выведите одно положительное целое число $$$k$$$ — максимально возможную длину $$$a$$$. Во второй строке выведите $$$k$$$ целых чисел $$$a_1, a_2, \ldots, a_k$$$ — последовательность длины $$$k$$$, удовлетворяющую ограничениям из условия задачи.

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

Пример
Входные данные
4
2
360
4999999937
4998207083
Выходные данные
1
2 
3
2 2 90 
1
4999999937 
1
4998207083