Factorial Prime Factorization

Given an integer \(N\) satisfying \(3 \le N \le 10^6\), compute the prime factorization of \(N!\) according to the arithmetic fundamental theorem. That is, find all primes \(p_i\) and their exponents \(c_i\) such that

\[ N! = \prod_{i} p_i^{c_i} \]

You can compute the exponent \(c_i\) for each prime \(p_i\) using Legendre's formula: \[ c_i = \sum_{k \ge 1} \left\lfloor \frac{N}{p_i^k} \right\rfloor \]

Output each prime and its exponent in increasing order of primes, each pair on a new line in the format "p c".

inputFormat

The input consists of a single integer \(N\) on one line.

outputFormat

For each prime factor \(p\) of \(N!\) (i.e. for each prime \(p\) such that \(p \le N\)), output a line containing two integers \(p\) and \(c\), where \(c\) is the exponent of \(p\) in the prime factorization of \(N!\). The primes should be output in increasing order.

sample

3

2 1
3 1