Description

已知对于任意整数N都可以按照以下格式进行质因数分解：

请你编程实现：给定正整数n，试把n!分解质因数，输出pi和ri。

Format

Input

一个正整数n

Output

输出若干行，每行pi和ri（用空格隔开）

Samples

5

2 3
3 1
5 1

Limitation

对于100%的数据$n<=10^6$