베르트랑 공준에 도전하기

베르트랑 공준은 임의의 $n \ge 2$에 대해 $n < p < 2n$을 만족하는 소수 $p$가 존재한다고 말한다. 베르트랑은 1845년에 이를 추측으로 제시했고, $n = 3\,000\,000$까지 검증했다. 체비쇼프는 1852년에 이를 증명했다.

페탸는 베르트랑의 업적을 따라 해 보고, 여러 $n$에 대해 공준이 성립하는지 확인하려 한다. 다만 체비쇼프의 증명은 의심하지 않으므로 목표를 조금 바꿨다. 주어진 $n$에 대해 $n$과 $2n$ 사이에 있는 합성수로 이루어진 구간 중 가장 긴 것을 찾는다.

$n < l \le r < 2n$을 만족하고, $l$부터 $r$까지의 모든 수가 합성수이며, $r - l$이 최대가 되는 $l$과 $r$을 구하라. 그런 구간이 여러 개이면 $l$이 가장 작은 구간을 출력한다.

정수 $n$이 한 개 주어진다. ($3 \le n \le 10^7$)

$l$과 $r$을 출력한다.