Problem Description

Given an integer $N (3 \le N \le 10^6)$, factorize the factorial $N!$ into prime factors. You only need to output $p_i$ and $c_i$ in the form required by the Fundamental Theorem of Arithmetic.

Input Format

An integer $N$.

Output Format

The prime factorization result of $N!$, consisting of several lines. Each line contains a pair $p_i, c_i$, meaning there is a term $p_i^{c_i}$. Output in increasing order of $p_i$.

5

2 3
3 1
5 1

Hint

Translated by ChatGPT 5