Alice 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.

Difficulty: interview

Starter code:

Solutions:
from math import floor, sqrt
import bisect

import math


def rwh_primes2(n):
    # https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    correction = (n%6>1)
    n = {0:n,1:n-1,2:n+4,3:n+3,4:n+2,5:n+1}[n%6]
    sieve = [True] * (n//3)
    sieve[0] = False
    for i in range(int(n**0.5)//3+1):
      if sieve[i]:
        k=3*i+1|1
        sieve[      ((k*k)//3)      ::2*k]=[False]*((n//6-(k*k)//6-1)//k+1)
        sieve[(k*k+4*k-2*k*(i&1))//3::2*k]=[False]*((n//6-(k*k+4*k-2*k*(i&1))//6-1)//k+1)
    return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]


k = int(input())

primes = rwh_primes2(k)

a = 1
p2 = 2
for i in primes[::-1]:
    if k%i == 0:
        p2 = i
        break

xx = range(k-p2+1, k+1)
#print(list(xx))
if p2>240:
    p1 = primes[bisect.bisect_left(primes, int(math.ceil(xx[0]/2)))]
    print(p1+1)
else:
    ans = k
    p1 = 1
    for x1 in xx:
        for i in primes[::-1]:

            if i >= x1:
                continue

            if x1 % i == 0:
                p1 = i
                break
        ans = min(ans, x1-p1+1)

    print(ans)

x2 = int(input())

n = 1000001
max_prime_div = [0] * n
sieve = list(range(n))
sieve[1] = 0
for i in sieve:
    if i > 1 and sieve[i]:
        for j in range(2 * i, n, i):
            sieve[j] = 0
            max_prime_div[j] = i

min_x0 = n
for x in range(x2 - max_prime_div[x2] + 1, x2 + 1):
    max_div = max_prime_div[x]
    tmp = x - max_div + 1
    if max_div and tmp < min_x0:
        min_x0 = tmp
print(min_x0)

x2 = int(input())

n = 1000001
max_prime_div = [0] * n
sieve = list(range(n))
sieve[1] = 0
for i in sieve:
    if sieve[i]:
        for j in range(2 * i, n, i):
            sieve[j] = 0
            max_prime_div[j] = i

min_x0 = n
for x in range(x2 - max_prime_div[x2] + 1, x2 + 1):
    max_div = max_prime_div[x]
    tmp = x - max_div + 1
    if max_div and tmp < min_x0:
        min_x0 = tmp
    if max_div and x // max_div == 2:
        break
print(min_x0)

import array

x2 = int(input())

n = 1000001
max_prime_div = array.array('i', [0] * n)
sieve = array.array('i', list(range(n)))
sieve[1] = 0
for i in sieve:
    if sieve[i]:
        for j in range(2 * i, n, i):
            sieve[j] = 0
            max_prime_div[j] = i

min_x0 = n
for x in range(x2 - max_prime_div[x2] + 1, x2 + 1):
    max_div = max_prime_div[x]
    tmp = x - max_div + 1
    if max_div and tmp < min_x0:
        min_x0 = tmp
    if max_div and x // max_div == 2:
        break
print(min_x0)

import array

x2 = int(input())

n = 1000001
max_prime_div = array.array('i', [0] * n)
sieve = array.array('i', list(range(n)))
sieve[1] = 0
for i in sieve:
    if sieve[i]:
        for j in range(2 * i, n, i):
            sieve[j] = 0
            max_prime_div[j] = i

min_x0 = n
for x in range(x2 - max_prime_div[x2] + 1, x2 + 1):
    max_div = max_prime_div[x]
    tmp = x - max_div + 1
    if max_div and tmp < min_x0:
        min_x0 = tmp
    if max_div and x // max_div == 2:
        break
print(min_x0)

x=int(input())
p=[1]*(x+1)
a=2
p[0]=0
p[1]=0
while a<=x:
    if p[a]:
        for i in range(a**2,x+1,a):
            p[i]=0
    a+=1
c=[]
for i in range(2,len(p)-1):
    if p[i]:
        c.append(i)
for i in range(len(c)-1,-1,-1):
    if not x%c[i]:
        low=c[i]
        break
poss=[i for i in range(max(x-low+1,3),x)]
ans=poss[0]
l=0
r=1
try:
    while poss[0]>=c[r+1]*2:
        r+=1
except IndexError:
    ...
for i in poss:
    while i-c[l]+1>=ans:
        l+=1
    if c[r]*2<=i:
        r+=1
    if l>r:
        break
    for j in range(l,r+1):
        if not i%c[j] and i-c[j]>1:
            ans=min(ans,i-c[j]+1)
print(ans)

x=int(input())
p=[1]*(x+1)
a=2
p[0]=0
p[1]=0
while a<=x:
    if p[a]:
        for i in range(a**2,x+1,a):
            p[i]=0
    a+=1
c=[]
for i in range(2,len(p)-1):
    if p[i]:
        c.append(i)
for i in range(len(c)-1,-1,-1):
    if not x%c[i]:
        low=c[i]
        break
poss=[i for i in range(max(x-low+1,3),x)]
ans=poss[0]
l=0
r=1
try:
    while poss[0]>=c[r+1]*2:
        r+=1
except IndexError:
    ...
for i in poss:
    while i-c[l]+1>=ans:
        l+=1
    if c[r]*2<=i:
        r+=1
    if l>r:
        break
    for j in range(l,r+1):
        if not i%c[j] and i-c[j]>1:
            ans=min(ans,i-c[j]+1)
print(ans)

n = int(input())

siv = [0 for _ in range(n + 1)]

for i in range(2, n + 1):
    if siv[i] == 0:
        for j in range(i + i, n + 1, i):
            siv[j] = i
    siv[i] = i - siv[i] + 1;

ans = n
for i in range(siv[n], n + 1):
    ans = min(ans, siv[i])

print(ans)


x2 = int(input())

s = [-1] * (x2 + 1)
for i in range(2, x2+1):
	if s[i] == -1:
		for j in range(i, x2+1, i):
			s[j] = i
	
ans = x2
for x1 in range(x2 - s[x2] + 1, x2 + 1):
	x0 = x1 - s[x1] + 1
	if x0 > 1:
		ans = min(ans, x0)

print(ans)


nmax = 1000010
primes = [0 for i in range(nmax)]

def get_primes():
    nonlocal primes

    n = 2
    while n < nmax:
        num = 2*n
        while num < nmax:
            primes[num] = n
            num += n
        num = n + 1
        while num < nmax and primes[num] != 0 :
            num += 1
        n = num

def algo(x2):
    nonlocal primes

    p2 = primes[x2]
    min_x1 = x2-p2+1
    min_x0 = nmax

    for x1 in range(min_x1, x2+1):
        p1 = primes[x1]
        x0 = x1 - p1 + 1

        if x0 < min_x0:
            min_x0 = x0
            # print("p1 is ", p1, " for ", x0)
    return min_x0


x2 = int(input().strip())
get_primes()
print(algo(x2))


x2 = int(input())
s = [-1] * (x2+1)
for i in range(2, x2+1):
    if s[i] == -1:
        for j in range(i, x2+1, i):
            s[j] = i;
ans = x2
for x1 in range(x2-s[x2]+1, x2+1):
    x0 = x1 - s[x1] + 1
    if x0 > 1:
        ans = min(ans, x0)
print(ans)


from sys import stdin
maxn = 1000006
prime = [0] * maxn
def getPrimes():
    n = 2
    while(n < maxn):
        num = n*2
        while(num < maxn):
            prime[num] = n
            num += n
        num = n + 1
        while(  num < maxn and prime[num]!= 0 ):
            num += 1
        n = num


def main():
    getPrimes()
    n = int(stdin.readline().strip())
    a = 0
    b = prime[n]
    x0 = 9999999
    for i in range(n-b+1,n+1):
        
        a = prime[i]
        x0 = min(i-a+1,x0)
        #print("i",i,"prime[i]",prime[i],"x0",x0)
    print(x0)

main()


n = int(input())

ans = n

f = [0]*(n+1)

for i in range(2, n+1):

    if f[i]==0:

        for j in range(i*2, n+1, i):

            f[j] = i

    f[i] = i-f[i]+1

for i in range(f[n], n+1):

    ans = min(ans, f[i])

print(ans)



# Made By Mostafa_Khaled


def max_less_prime_divisor(n): # 1 for primes
    d, max_d = 2, 1
    while d * d <= n:
        while n % d == 0:
            max_d = d
            n //= d
        d += 1
    return n if n != 1 and max_d != 1 else max_d

n = int(input())
m = n - max_less_prime_divisor(n) + 1
answer = m
is_prime = [True] * m
for i in range(2, m):
    if is_prime[i]:
        d = (m - 1) - (m - 1) % i
        if d + i <= n:
            answer = min(answer, d + 1)
        for j in range(i * i, m, i):
            is_prime[j] = False
print(answer)
    


n = int(input())

is_prime = [True] * n
for i in range(2, n):
    if is_prime[i]:
        for j in range(i * i, n, i):
            is_prime[j] = False
primes = [i for i in range(2, n) if is_prime[i]]

m = n - 1
for p in primes:
    if n % p == 0:
        m = n - p

answer = m + 1
for p in primes:
    if p > m:
        break
    d = m - m % p
    if d + p <= n:
        answer = min(answer, d + 1)
print(answer)
    


n = int(input())

is_prime = [True] * n
for i in range(2, n):
    if is_prime[i]:
        for j in range(i * i, n, i):
            is_prime[j] = False
primes = [i for i in range(2, n) if is_prime[i]]

m = n - 1
for p in primes:
    if n % p == 0:
        m = n - p

answer = m + 1
for p in primes:
    if p > m:
        break
    d = m - m % p
    if d + p <= n:
        answer = min(answer, d + 1)
print(answer)
    


n = int(input())
is_prime = [True] * n
for i in range(2, n):
    if is_prime[i]:
        for j in range(i * i, n, i):
            is_prime[j] = False
primes = [i for i in range(2, n) if is_prime[i]]
m = n - 1
for p in primes:
    if n % p == 0:
        m = n - p
answer = m + 1
for p in primes:
    if p > m:
        break
    d = m - m % p
    if d + p <= n:
        answer = min(answer, d + 1)
print(answer)


x = int(input())
n = x
vis = [False for i in range(n+1)]
flag = [0 for i in range(n+1)]
for i in range(2, n+1):
    if not vis[i]:
        for j in range(i+i, n+1, i):
            vis[j] = True
            flag[j] = i
ans = x
for i in range(x - flag[x] + 1, x+1):
    ans = min(ans, i - flag[i] + 1)
print(ans)


# By Sieve of Erastoteles
def getPrimes(n):
	primes = [0 for _ in range(n + 1)] # Initialize 'primes' in 0
	for i in range(2, n + 1): # n + 1 is the last we will need
	    if not primes[i]: # if it is zero, apply algorithm
	        for j in range(2*i, n + 1, i):
	            primes[j] = i
	    primes[i] = i - primes[i] + 1; # Game
	# print(primes)
	return primes

x2 = int(input())
primes = getPrimes(x2)

res = x2
for i in range(primes[x2], x2 + 1):
	res = min(res, primes[i])

print(res)

n = int(input())

siv = [0 for _ in range(n+1)]

for i in range(2, n+1):
    if siv[i] == 0:
        for j in range(i+i, n+1, i):
            siv[j] = i
    siv[i] = i - siv[i] + 1;

result = n
for i in range(siv[n], n + 1):
    result = min(result, siv[i])

print(result)

x = int(input())

arr = [0 for i in range(x + 1)]

for i in range(2, x+1):
    if(arr[i] == 0):
        for j in range(i + i, x + 1, i):
            arr[j] = i
    arr[i] = i - arr[i] + 1;

result = x
for i in range(arr[x], x + 1):
    result = min(result, arr[i])

print(result)


lectura = int(input())
lista0 = [0]*(lectura+1)
for i in range(2, lectura+1):
    #print("i= "+str(i))
    if lista0[i]==0:
        for j in range(2*i, lectura+1, i):
            #print("j= "+str(j))
            lista0[j] = i
    lista0[i] = i-lista0[i]+1
conclusion = lectura
for i in range(lista0[lectura], lectura+1):
    conclusion = min(conclusion, lista0[i])
print(conclusion)