题目描述

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

输入格式

一个整数 $N$。

输出格式

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

5

2 3
3 1
5 1

输入样例 #2

63

输出样例 #2

2 57
3 30
5 14
7 10
11 5
13 4
17 3
19 3
23 2
29 2
31 2
37 1
41 1
43 1
47 1
53 1
59 1
61 1

输入样例 #3

97

输出样例 #3

2 94
3 46
5 22
7 14
11 8
13 7
17 5
19 5
23 4
29 3
31 3
37 2
41 2
43 2
47 2
53 1
59 1
61 1
67 1
71 1
73 1
79 1
83 1
89 1
97 1

数据范围

$3 \le N \le 10^6$