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을 말한다.