Factoring into Prime Factors - 2

For the given number N, provide its prime factorization.

Input

The input consists of a single line containing the number N (2 ≤ N ≤ 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