Prime Factors with Exponents

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Given an integer $n\ge2$, express it as a product of powers of primes. For each prime factor $p$, let $e$ be the multiplicity of $p$ in the factorization (the largest exponent such that $p^e$ divides $n$). Print each pair $p,e$ on its own line, with prime factors in strictly increasing order. Print each distinct prime exactly once.

Input

One line contains one integer $n$.

Output

Print two integers $p$ and $e$ separated by one space on each line, in increasing order of $p$.

Subtasks

• Subtask 1 (20%): $2\le n\le10^4$.
• Subtask 2 (30%): $2\le n\le10^8$.
• Subtask 3 (50%): $2\le n\le10^{12}$.

Examples

Example 1

Input:

360

Output:

2 3
3 2
5 1

Explanation: Since $360=2^3\cdot3^2\cdot5$, print prime-exponent pairs (2,3), (3,2), (5,1) in increasing prime order.

Example 2

Input:

13

Output:

13 1

Explanation: 13 is prime, so its factorization contains just the pair 13 1.

Example 3

Input:

64

Output:

2 6

Explanation: Dividing 64 by 2 six times reaches 1, hence $64=2^6$ and the only line is 2 6.