Hide

Problem D
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

Please log in to submit a solution to this problem

Log in