Factoring into Prime Factors - 2

Input

The input consists of a single line containing the number $N$ (2 \leq N \leq 100000).

Output

For each prime factor of $N$, output two numbers on a separate line: the prime divisor and its exponent in the factorization. Do not include any divisor with an exponent of $0$. Present the pairs in ascending order based on the divisor. Refer to the examples for clarity.

Examples