题目描述

对N!进行质因子分解，输出所有质因数及其对应的指数，按质因数从小到大排列。

输入格式

一个正整数N（N ≤ 10000）

输出格式

若干行，每行两个正整数p和a，表示N!包含a个质因子p

样例

输入

10

输出

2 8
3 4
5 2
7 1