算术基本定理： 任何一个大于 1 的自然数可以分解成一些素数的乘积；并且在不计次序的情况下，这种分解方式是唯一的。算术基本定理起源很早，但将其提炼、明确表述成一条定理，使其在初等数论中获得基础性的地位，却经历了一段较长的时间。（来自百度百科）。

即： N = p_1^{a_1} \times p_2^{a_2} \cdots p_k^{a_k} ，其中 p_1 \lt p_2 \lt \cdots \lt p_k 。

小Z在很小的时候，就学会了阶乘，即 N! = 1 \times 2 \times \cdots \times N

现在小Z提出，将 N! 根据算术基本定理进行分解。

输入一行，一个整数 N。

分解后的结果，共若干行，每行一对 p_i,a_i，表示含有 p_i^{a_i}项。按照 p_1 从小到大的顺序输出。

【样例解释】

5! = 120

120 = 2^3 \times 3^1 \times 5^1

【数据范围】

3 \le N \le 10^6

2025年11月婺城区第三届青少年信息素养大赛初中组试题

市赛