No testdata at current.

Background

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

Input

一个整数$N$

Output

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

Samples

5

2 3
3 1
5 1

Limitation

$5!=120=2^3*3*5$