Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Primal Sport

time limit per test

1.5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAlice and Bob begin their day with a quick game. They first choose a starting number *X*_{0} ≥ 3 and try to reach one million by the process described below.

Alice goes first and then they take alternating turns. In the *i*-th turn, the player whose turn it is selects a prime number smaller than the current number, and announces the smallest multiple of this prime number that is not smaller than the current number.

Formally, he or she selects a prime *p* < *X*_{i - 1} and then finds the minimum *X*_{i} ≥ *X*_{i - 1} such that *p* divides *X*_{i}. Note that if the selected prime *p* already divides *X*_{i - 1}, then the number does not change.

Eve has witnessed the state of the game after two turns. Given *X*_{2}, help her determine what is the smallest possible starting number *X*_{0}. Note that the players don't necessarily play optimally. You should consider all possible game evolutions.

Input

The input contains a single integer *X*_{2} (4 ≤ *X*_{2} ≤ 10^{6}). It is guaranteed that the integer *X*_{2} is composite, that is, is not prime.

Output

Output a single integer — the minimum possible *X*_{0}.

Examples

Input

14

Output

6

Input

20

Output

15

Input

8192

Output

8191

Note

In the first test, the smallest possible starting number is *X*_{0} = 6. One possible course of the game is as follows:

- Alice picks prime 5 and announces
*X*_{1}= 10 - Bob picks prime 7 and announces
*X*_{2}= 14.

In the second case, let *X*_{0} = 15.

- Alice picks prime 2 and announces
*X*_{1}= 16 - Bob picks prime 5 and announces
*X*_{2}= 20.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/27/2023 14:22:43 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|