소인수 배열

$1$보다 큰 모든 자연수는 소수들의 곱으로 유일하게 나타낼 수 있다. 하지만 이 소인수들을 나열하는 순서는 여러 가지가 있을 수 있다.

$10 = 2 \times 5 = 5 \times 2$

$20 = 2 \times 2 \times 5 = 2 \times 5 \times 2 = 5 \times 2 \times 2$

$k$의 소인수를 나열하는 서로 다른 방법의 수를 $f(k)$라고 하면 $f(10) = 2$, $f(20) = 3$이다.

양의 정수 $n$이 주어질 때, $f(k) = n$을 만족하는 $k$는 항상 하나 이상 존재한다. 이러한 $k$ 중에서 가장 작은 값을 구하는 프로그램을 작성하시오.

입력은 최대 1,000개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 한 줄에 하나씩 주어진다. 각 테스트 케이스는 $n < 2^{63}$인 양의 정수 $n$이다. 입력은 파일의 끝(EOF)까지 계속된다.

각 테스트 케이스마다 한 줄에 $n$과, $f(k) = n$을 만족하는 가장 작은 $k > 1$을 공백 하나로 구분하여 출력한다. 주어지는 입력은 항상 $k < 2^{63}$인 경우만 포함한다.