题目描述

给定整数 $\red N$ ，试把阶乘 $\red{N!}$ 分解质因数，按照算术基本定理的形式输出分解结果中的 $\red{p_i}$ 和 $\red{c_i}$ 即可。

输入格式

一个整数$\red N$。

输出格式

$\red {N!}$ 分解质因数后的结果，共若干行，每行一对 $\red{pi}$,$\red{c_i}$，表示含有 $\red{p_i c_i}$项。按照$\red{p_i}$从小到大的顺序输出。

样例

输入样例

5

输出样例

2 3
3 1
5 1

提示

$\red{1\leq N\leq106}$

$\red{5!=120=2^3\times 3\times 5}$