Вам задано целое число \(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\) независимых наборов тестовых данных.
Выходные данные
Выведите ответ на каждый набор тестовых данных: в первой строке выведите одно положительное целое число \(k\) — максимально возможную длину \(a\). Во второй строке выведите \(k\) целых чисел \(a_1, a_2, \ldots, a_k\) — последовательность длины \(k\), удовлетворяющую ограничениям из условия задачи.
Если существует несколько возможных ответов, вы можете вывести любой из них. Можно доказать, что хотя бы одна корректная последовательность всегда существует для любого целого числа \(n > 1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2
360
4999999937
4998207083
|
1
2
3
2 2 90
1
4999999937
1
4998207083
|