Factorial Prime Factorization Problem

Given an integer N, factorize the factorial N! into its prime factors. Output the result in the form of the Fundamental Theorem of Arithmetic: for each prime factor p_i, output p_i and its exponent c_i.

Input Format
A single integer N.

Output Format
Several lines, each containing a pair p_i c_i, meaning p_i^c_i appears in the factorization of N!. Output the pairs in increasing order of p_i.

Data Range
3 ≤ N ≤ 10⁶

Sample Input

5

Sample Output

2 3
3 1
5 1

Sample Explanation
5! = 120 = 2³ · 3 · 5