拆解高塔

间隙丈量完了，密码是12。但12不是一个简单的数——在Zero的加密体系里，12代表一座高塔。

"高塔？"CC问。

"阶乘。"你说，"$12!$。12的阶乘——从1乘到12。"

"多大？"

"479001600。"你说，"将近5亿。"

"这咋拆？"

"质因数分解。"你说，"把$12!$拆成质数的幂的乘积。比如$12!=2^{10}\times 3^5\times 5^2\times 7^1\times 11^1$。"

"拆这个干啥？"

"因为Echo-0把最核心的秘密，藏在了阶乘的质因数里。"Echo说，"指数的模式——10,5,2,1,1——就是密钥。"

"指数模式？"

"对。"你说，"每个质数$p$在$n!$中的指数是$\lfloor n/p\rfloor+\lfloor n/p^2\rfloor+\dots$。"

"算起来快吗？"

"快。"你说，"$O(\log n)$就能算一个质数的指数。"

你开始拆解。$2^{10}$，$3^5$，$5^2$，$7^1$，$11^1$。

"指数和。"你说，"10+5+2+1+1=19。"

"19？"

"对。"你说，"19——又一个密码碎片。"

CC在手臂上找空位——已经刻了45360和12，没地方了。

"刻这。"她指着金属肩膀的另一侧，"这边空。"

"你把自己当记事本？"

"对。"她说，"我是活的记事本。不会丢，不会坏。"

"除非你被炸了。"

"那你们就记住。"她说，"记住这些数。"

Echo把19加进她的记忆——不是刻，是存，像呼吸一样自然。

"记住了。"她说，"不会忘。"

题目描述

给定$n$，对$n!$进行质因数分解，输出每个质因子的指数。

输入格式

一个整数$n$。

输出格式

每行一个质数和对应的指数。

输入样例

5

输出样例

2 3
3 1
5 1

提示

• $n!$中质数$p$的指数：$\sum_{i=1}^{\infty}\lfloor n/p^i\rfloor$。
• 先筛出所有$\le n$的质数，然后对每个质数算指数。