시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB22661248114055.019%

문제

백준 온라인 저지의 송년대회 Good Bye BOJ, 2021!의 개최일은 2021년 12월 31일이다. 원이는 대회가 개최된다는 사실이 기뻐 제목을 뚫어져라 보다가 2021이 무언가 특별하다는 사실을 깨달았다.

그렇다. 2021은 연속한 두 소수 43과 47의 곱이다. 다음에 이런년도가 오려면 무려 470년 뒤인 2491년이 되어야 한다. 원이는 어떤 수가 연속한 두 소수의 곱으로 이루어져 있으면 특별한 수라 부르기로 하였다.

주어진 수보다 큰 특별한 수 중 가장 작은 수를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 주어진 수 $N$이 주어진다.

출력

첫 번째 줄에 $N$보다 큰 특별한 수 중 가장 작은 수를 출력하여라.

제한

  • $1 \le N \le 10\,000$
  • $N$은 정수이다.

예제 입력 1

2020

예제 출력 1

2021

예제 입력 2

2021

예제 출력 2

2491

노트

  • 소수란 2 이상의 정수 중에서, 1과 자기 자신으로만 나누어떨어지는 수이다.
  • $p$와 $q$가 소수이며 $p$ 초과, $q$ 미만의 소수가 존재하지 않을 때, $p$와 $q$를 연속한 소수라고 한다.

출처

Contest > Good Bye, BOJ > Good Bye, BOJ 2021! A번