Problem C
Fundamental Neighbors

The fundamental theorem of arithmetic says that any natural number greater than one can be written uniquely as the product of prime numbers. For example: $3=3^1$, $4=2^2$, $6=2^1\times 3^1$, $72=2^3\times 3^2$, and in general,

for prime numbers $p_1$ through $p_k$ and exponents $e_1$ through $e_k$.

For this problem, given an integer $n\ge 2$, determine what we will call the ‘neighbor’ of $n$. The neighbor is the integer you get by swapping the $p_i$ and $e_i$ values in the prime factorization of $n$. That is, if $n$ is written in prime factorization as above, the neighbor of $n$ is

For example, if $n=2000=2^4\times 5^3$ then its neighbor is $4^2\times 3^5=3888$.

Input

Input is a sequence of up to $20000$ integers, one per line. Each integer is in the range $2\le n<2^{31}$. Input ends at the end of file.

Output

For each $n$, print $n$ followed by its neighbor. Each neighbor is in the range $[1,2^{31})$.

2
3
4
5
6
7
8
9
10
72
200

2 1
3 1
4 4
5 1
6 1
7 1
8 9
9 8
10 1
72 72
200 288