Description

Perform the prime factorization of $N!$.

Input Format

The input consists of a single line containing a positive integer $N$, with $N \leq 10000$.

Output Format

Output multiple lines. Each line contains two positive integers $p$ and $a$, separated by a single space, indicating that $N!$ contains $a$ copies of the prime factor $p$. Output them in increasing order of $p$.

10

2 8
3 4
5 2
7 1

Hint

$10! = 3628800 = (2^8) \times (3^4) \times (5^2) \times 7$.

Translated by ChatGPT 5