Primal Sport

Alice and Bob는 간단한 게임으로 하루를 시작한다. 이들은 먼저 시작 수 X0 ≥ 3을 고르고, 아래에 설명된 과정을 통해 백만에 도달하려 한다.

Alice가 먼저 시작하고, 이후 두 사람이 번갈아 차례를 진행한다. i-th 차례에는 차례인 플레이어가 현재 수보다 작은 소수를 선택하고, 이 소수의 배수 중 현재 수보다 작지 않은 가장 작은 수를 말한다.

형식적으로, 그 또는 그녀는 소수 p < Xi - 1을 선택한 다음, p가 Xi를 나누도록 하는 최소의 Xi ≥ Xi - 1을 찾는다. 선택한 소수 p가 이미 Xi - 1을 나눈다면 수가 변하지 않음에 유의한다.

Eve는 두 차례가 끝난 뒤의 게임 상태를 목격했다. Given X2, 가능한 가장 작은 시작 수 X0를 알아내도록 그녀를 도와주자. 플레이어들이 반드시 최적으로 플레이하는 것은 아님에 유의한다. 가능한 모든 게임 진행을 고려해야 한다.

입력에는 정수 하나 X2 (4 ≤ X2 ≤ 106)가 주어진다. 정수 X2는 합성수, 즉 소수가 아님이 보장된다.

가능한 X0의 최솟값인 정수 하나를 출력한다.

첫 번째 테스트에서 가능한 가장 작은 시작 수는 X0 = 6이다. 가능한 게임 진행 중 하나는 다음과 같다.

• Alice는 소수 5를 선택하고 X1 = 10이라고 말한다
• Bob은 소수 7을 선택하고 X2 = 14라고 말한다.

두 번째 경우에는 X0 = 15로 두자.

• Alice는 소수 2를 선택하고 X1 = 16이라고 말한다
• Bob은 소수 5를 선택하고 X2 = 20이라고 말한다.