가짜 소수

지구이는 100억쯤 되는 큰 수가 소수인지 판별해야만 풀리는 문제를 만났다. 2부터 $\sqrt{N}$까지 모든 수로 나눠 보는 코드를 짰지만 한 시간이 지나도 결과가 나오지 않았다. 검색해 보니 페르마 소정리가 있었다.

소수 $p$와 $\gcd(a, p) = 1$인 모든 자연수 $a$에 대하여 $a^{p-1} \equiv 1 \pmod p$이다.

지구이는 이것을 거꾸로 써서 $2^{n-1} \equiv 1 \pmod n$이면 $n$을 소수로 판정하는 코드를 짰다. 그런데 이 코드는 561을 소수로 분류했다. 포기하지 않은 지구이는 밑을 늘려서 다음 판정법을 쓰기로 했다.

자연수 $n$에 대하여 2 이상 500 이하의 모든 정수 $a$가 $a^{n-1} \equiv 1 \pmod n$을 만족하면 $n$을 소수로 판정하고, 하나라도 만족하지 않으면 합성수로 판정한다.

백만까지 컴퓨터로 확인해 본 지구이는 자신만만하게 답을 제출했지만 또 틀렸다. $n > 500$이면 소수는 언제나 소수로 판정되므로, 이 판정법이 틀리는 경우는 합성수를 소수로 판정하는 경우뿐이다. 이런 $n$을 반례라고 부르자.

지구이에게 반례를 알려주자. 정수 $L$이 주어질 때, $L$보다 큰 가장 작은 반례와 그 반례의 가장 작은 소인수를 구한다.

첫 줄에 정수 $L$이 주어진다. ($500 \le L \le 10^{12}$)

첫 줄에 $L$보다 큰 가장 작은 반례 $n$과 $n$의 가장 작은 소인수 $m$을 공백으로 구분해 출력한다. 답이 되는 $n$은 항상 $10^{15}$ 이하이고, $m$은 $1 < m < n$을 만족한다.