题目描述

将 $n!$ 分解质因数。把每个出现的质数及其在 $n!$ 中出现的个数输出，质数按从小到大的顺序排列。

输入格式

一行，一个正整数 $n$（$n \le 10000$）。

输出格式

每行输出两个整数 $p$ 和 $cnt$，分别表示质数 $p$ 及其在 $n!$ 中出现的次数，相邻两个整数用一个空格隔开。

样例

6

2 4
3 2
5 1

说明/提示

对每个 $2 \le p \le n$ 的质数，用 Legendre 公式 $cnt = \lfloor n/p \rfloor + \lfloor n/p^2 \rfloor + \lfloor n/p^3 \rfloor + \cdots$ 计算其在 $n!$ 中的指数。可先用筛法得到 $n$ 以内的所有质数。