ICPC 2013 · Problem D · Factors

Time Limit: 2 seconds

The fundamental theorem of arithmetic states that every integer greater than 1 can be uniquely repre- sented as a product of one or more primes. While unique, several arrangements of the prime factors may be possible. For example:

$10 = 2\cdot 5$ $20 = 2\cdot 2\cdot 5$

$= 5\cdot 2$ $= 2\cdot 5\cdot 2$

$= 5\cdot 2\cdot 2$

Let $f(k)$ be the number of different arrangements of the prime factors of $k$. So $f(10) = 2$ and $f(20) = 3$.

Given a positive number $n$, there always exists at least one number $k$ such that $f(k) = n$. We want to know the smallest such $k$.

Input

The input consists of at most $1 000$ test cases, each on a separate line. Each test case is a positive integer $n <2^{63}$.

Output

For each test case, display its number $n$ and the smallest number $k > 1$ such that $f(k) = n$. The numbers in the input are chosen such that $k <2^{63}$.

Sample Input 1

1
2
3
105

Sample Output 1

1 2
2 6
3 12
105 720

ACM-ICPC World Finals 2013 Problem D: Factors