레이팅 미적용설명
산술의 기본 정리에 따르면 1보다 큰 모든 정수는 하나 이상의 소수의 곱으로 유일하게 표현된다(rep\(re- se\)nted). 유일하긴 하지만, 소인수들의 배열 방법은 여러 가지일 수 있다. 예를 들면 \(10 = 2 \cdot 5 20 = 2 \cdot 2 \cdot 5 = 5 \cdot 2 = 2 \cdot 5 \cdot 2 = 5 \cdot 2 \cdot 2\) \(f\)(\(k\))를 \(k\)의 소인수들의 서로 다른 배열의 수라고 하자. 그러면 \(f\)(10) = 2이고 \(f\)(20) = 3이다. 양수 \(n\)이 주어지면 \(f\)(\(k\)) = \(n\)인 수 \(k\)가 항상 적어도 하나 존재한다. 그런 \(k\) 중 가장 작은 것을 알고 싶다.
제약
입력 형식
입력은 최대 1 000개의 테스트 케이스로 이루어지며, 각각 별개의 줄에 주어진다. 각 테스트 케이스는 양의 정수 \(n < 2^{63}\)이다.
출력 형식
각 테스트 케이스마다 그 수 \(n\)과, \(f\)(\(k\)) = \(n\)을 만족하는 가장 작은 수 \(k > 1\)을 출력한다. 입력의 수들은 \(k < 2^{63}\)이 되도록 선택되어 있다.
예제 1
입력
1
2
3
105
출력
1 2
2 6
3 12
105 720
문제 정보