阶乘分解质因数

题目描述

给定整数 N(1≤N≤10^6 )，试把阶乘 N! 分解质因数,按照算术基本定理的形式输出分解结果中的 Pi和Ci 即可。

输入描述:

一个整数N。

输出描述:

N! 分解质因数后的结果，共若干行，每行一对 Pi,Ci ，表示含有Pi^Ci 项。按照Pi从小到大的顺序输出。

示例输入

5

输出

2 3 3 1 5 1

说明

5! = 120 = 2^3 * 3 *5