Background

Special for beginners, ^_^

Description

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

Format

Input

一个整数N。.

Output

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

Samples

5

2 3
3 1
5 1

Limitation

1s, 1024KiB for each test case.