# This content is archived!

For the 2018-2019 school year, we have switched to using the WLMOJ judge for all MCPT related content. This is an archive of our old website and will not be updated.

# Problem

It is a well-known fact that every natural number has a unique prime factorization. That is, you can uniquely express each natural number $N$ as:

N = P_1^{M_1} \times P_2^{M_2} \times \ldots \times P_K^{M_K}

Where $P_1 \leq P_2 \leq \ldots \leq P_K$ are prime numbers. For example, $28 = 22 \times 7$ and $3645 = 36 \times 5$.

In general, finding the prime factorization of large numbers is difficult to do (and serves as a basis for many cryptographic systems). However, in some special cases it is easy to find a number’s prime factorization.

One such case is when a number is a power of a smaller number. Given a number $N$, can you figure out the prime factorization of $N^N$?

# Input

Each test case contains one integer $N (2 \leq N \leq 2^{57})$

# Output

For each test case, output, on one line, prime factorization of the number.

# Editorial

Read only if you are stuck or have already solved the problem.