1보다 큰 모든 자연수는 하나 또는 그 이상의 소수의 곱으로 유일하게 나타낼 수 있다. 하지만, 이러한 소인수들을 배열하는 방법은 여러 가지가 있을 수 있다.

10 = 2×5 = 5×2

20 = 2×2×5 = 2×5×2 = 5×2×2

f(k)를 k의 소인수를 배열한 방법의 수라고 하면, f(10) = 2, f(20) = 3이 된다.

양의 정수 n이 주어진다. 이때, f(k) = n을 만족하는 k는 항상 적어도 하나 존재한다. 이때, 가장 작은 k를 구하는 프로그램을 작성하시오.

입력 형식

입력은 많아야 1,000개의 테스트 케이스로 이루어져 있고, 한 줄에 하나씩 주어진다. 각 테스트 케이스는 n < 2⁶³인 양의 정수이다.

출력 형식

각 테스트 케이스에 대해서, n을 출력하고 f(k) = n 인 가장 작은 k > 1을 출력한다. k < 2⁶³인 입력만 주어진다.

예제 입력

1
2
3
105

예제 출력

1 2
2 6
3 12
105 720