OpenKattis
National University of Singapore

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,

\[ n = p_1^{e_1}\times p_2^{e_2}\times \cdots \times p_ k^{e_ k} \]

for prime numbers $p_1$ through $p_ k$ and exponents $e_1$ through $e_ k$.

For this problem, given an integer $n \geq 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

\[ e_1^{p_1}\times e_2^{p_2}\times \cdots \times e_ k^{p_ k}. \]

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

Input

Input is a sequence of up to $20\, 000$ 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})$.

Sample Input 1 Sample Output 1
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