Humanity's Last Code Exam / 2013_D / Factors

### Problem Breakdown

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:

- 10=2⋅5
  - =5⋅2
- 20=2⋅2⋅5
  - =2⋅5⋅2
  - =5⋅2⋅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 1000 test cases, each on a separate line. Each test case is a positive integer n<2⁶³.

### 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⁶³.

### Sample Input 1

### Problem Breakdown

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:

- \(10 = 2 \cdot 5\)
  - \(= 5 \cdot 2\)
- \(20 = 2 \cdot 2 \cdot 5\)
  - \(= 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 1000 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