题目描述

输入 $n$，输出 $n!$ 的质因数分解。

• $0!=1$
• $n!=(n-1)!\times n$

输入格式

一个数 $n$。

输出格式

若干行，按质因子从小到大的顺序，输出每个质因子和对应的指数。

5

2 3
3 1
5 1

$5!=120=2^3+3^1+5^1$

数据规模与约定

对于 $100\%$ 的数据，$2 \le n \le 10^6$。