Alice and Bob begin their day with a quick game. They first choose a starting number *X*<sub class="lower-index">0</sub> ≥ 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* &lt; *X*<sub class="lower-index">*i* - 1</sub> and then finds the minimum *X*<sub class="lower-index">*i*</sub> ≥ *X*<sub class="lower-index">*i* - 1</sub> such that *p* divides *X*<sub class="lower-index">*i*</sub>. Note that if the selected prime *p* already divides *X*<sub class="lower-index">*i* - 1</sub>, then the number does not change.

Eve has witnessed the state of the game after two turns. Given *X*<sub class="lower-index">2</sub>, help her determine what is the smallest possible starting number *X*<sub class="lower-index">0</sub>. Note that the players don't necessarily play optimally. You should consider all possible game evolutions.
The input contains a single integer *X*<sub class="lower-index">2</sub> (4 ≤ *X*<sub class="lower-index">2</sub> ≤ 10<sup class="upper-index">6</sup>). It is guaranteed that the integer *X*<sub class="lower-index">2</sub> is composite, that is, is not prime.
In the first test, the smallest possible starting number is *X*<sub class="lower-index">0</sub> = 6. One possible course of the game is as follows: 
 -  Alice picks prime 5 and announces *X*<sub class="lower-index">1</sub> = 10 -  Bob picks prime 7 and announces *X*<sub class="lower-index">2</sub> = 14. 
In the second case, let *X*<sub class="lower-index">0</sub> = 15. 
 -  Alice picks prime 2 and announces *X*<sub class="lower-index">1</sub> = 16 -  Bob picks prime 5 and announces *X*<sub class="lower-index">2</sub> = 20.
14
6
20
15
8192
8191
1000000
998677
959806
239958
1452
1206
4
3
6
3
8
7
9
7
10
4
12
6
15
8
16
11
110880
55440
166320
110879
221760
110880
277200
138600
332640
166320
498960
332639
554400
415798
665280
498958
720720
540538
510510
255248
570570
285282
690690
460455
959818
239958
959878
239978
959902
239978
974847
324954
974859
324978
974931
324980
885481
442272
896809
447944
908209
453632
935089
467064
720721
355298
690691
342864
959903
479702
974932
470060
935090
463950
524288
524287
524289
174768
524286
262110
531441
526737
531442
262490
531440
265704
81
76
999958
250008
2048
1959
N = int(1e+6)
x2 = int(input())
x0 = int(1e+9)

was = [False] * N
p = [0] * N

for i in range(2, N):
    if was[i]:
        continue
    p[i] = i
    j = 2 * i
    while j < N:
        was[j] = True
        p[j] = max(p[j], i)
        j += i

for i in range(x2 - p[x2] + 1, x2 + 1):
    if p[i] == i:
        continue
    x0 = min(x0, i - p[i] + 1)

print(x0)
