Factors
The fundamental theorem of arithmetic states that every integer greater than 1 can be uniquely represented as a product of one or more primes. While unique, several arrangements of the prime factors may be possible. For example:
\begin{align*} 10 & = 2 \cdot 5 & 20 & = 2 \cdot 2 \cdot 5 \\ & = 5 \cdot 2 & & = 2 \cdot 5 \cdot 2 \\ & & & = 5 \cdot 2 \cdot 2 \end{align*}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 | Sample Output 1 |
|---|---|
1 2 3 105 |
1 2 2 6 3 12 105 720 |