← 返回题目列表

Codeforces · 1454/D

D. 数字进入序列

中文机器翻译题面 查看原题

给你一个整数 $$$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$$$);
- 对于从 $$$1$$$ 到 $$$k-1$$$ 的每个 $$$i$$$,$$$a_{i + 1}$$$ 可被 $$$a_i$$$ 整除;
- $$$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$$$,总是存在至少一个有效序列。

示例

输入 #1

4
2
360
4999999937
4998207083

输出 #1

1
2 
3
2 2 90 
1
4999999937 
1
4998207083