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: MEDIUM_HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
prime_number = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009]
num = int(input())
import math

def find_max_prime(val):
	result = 0
	if val in prime_number:
		return val
	for prime in prime_number:
		if prime > math.sqrt(val):
			break
		if val % prime == 0:
			temp = max(prime, find_max_prime(int(val / prime)))
			result = max(result, temp)
			break
	if result == 0:
		return val
	else:
		return result
prev = find_max_prime(num)
val = 10000000
for i in range(num - prev + 1, num + 1):
	if val < i / 2 + 1:
		continue
	k = find_max_prime(i)
	if k == i:
		continue
	else:
		val = min(val, i - k + 1)
print(val)


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(x0)
main()


def prime_factors(n):
	f = 2
	while f * f <= n:
		while n % f == 0:
			yield f
			n //= f
		f += 1
	if n > 1:
		yield n
x2 = int(input())
max_p_x2 = max([x for x in prime_factors(x2)])
ans = float('Inf')
for x1 in range(x2 - max_p_x2 + 1, x2 + 1):
	max_p_x1 = max([x for x in prime_factors(x1)])
	if x1 - max_p_x1 > 0:
		ans = min(ans, x1 - max_p_x1 + 1)
	else:
		ans = min(ans, x1)
	if ans < x1 // 2:
		break
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)


x = int(input())
pSieve = [True] * x
for i in range(2, x):
	if pSieve[i]:
		for j in range(i * i, x, i):
			pSieve[j] = False
primos = []
for i in range(2, x):
	if pSieve[i]:
		primos.append(i)
y = x - 1
for p in primos:
	if x % p == 0:
		y = x - p
z = y + 1
for i in primos:
	if i > y:
		break
	d = y - y % i
	if d + i <= x:
		z = min(z, d + 1)
print(z)


def lpf(n, m=0, i=2):
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
	return m - n
x = int(input())
a = x
for i in range(lpf(x, x + 1), x + 1):
	if lpf(i, i + 1) >= 3:
		a = min(lpf(i, i + 1), a)
print(a)


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)


x2 = int(input())
num = []
for val in range(1000010):
	num.append(0)
for i in range(2, x2):
	if num[i] == 0:
		for j in range(i + i, x2 + 1, i):
			num[j] = i
prim = x2 - num[x2] + 1
minn = 10000000
for i in range(prim, x2 + 1):
	minn = min(minn, i - num[i] + 1)
print(minn)


def gf(n):
	d = 2
	while d * d <= n:
		f = 1
		while n % d is 0:
			if f:
				yield d
			f = 0
			n //= d
		d += 1
	if n > 1:
		yield n
x2 = int(input())
print(min((x1 - p + 1 for x1 in range(x2 - max(gf(x2)) + 1, x2 + 1) for p in gf(x1) if p != x1)))


import sys
from math import floor, sqrt
from collections import Counter

def prime_sieve(n):
	flag = n % 6 == 2
	sieve = bytearray((n // 3 + flag >> 3) + 1)
	for i in range(1, int(n ** 0.5) // 3 + 1):
		if not sieve[i >> 3] >> (i & 7) & 1:
			k = 3 * i + 1 | 1
			for j in range(k * k // 3, n // 3 + flag, 2 * k):
				sieve[j >> 3] |= 1 << (j & 7)
			for j in range(k * (k - 2 * (i & 1) + 4) // 3, n // 3 + flag, 2 * k):
				sieve[j >> 3] |= 1 << (j & 7)
	return sieve

def prime_list(n):
	res = []
	if n > 1:
		res.append(2)
	if n > 2:
		res.append(3)
	if n > 4:
		sieve = prime_sieve(n + 1)
		res.extend((3 * i + 1 | 1 for i in range(1, (n + 1) // 3 + (n % 6 == 1)) if not sieve[i >> 3] >> (i & 7) & 1))
	return res

def main():
	mxs = [1] * 1000005
	ps = prime_list(1000000)
	for x in ps:
		for y in range(x + x, 1000005, x):
			mxs[y] = x
	n = int(sys.stdin.readline())
	mxp = mxs[n]
	ans = 10000000
	for y in range(n - mxp + 1, n):
		mxp2 = mxs[y]
		c = y - mxp2 + 1
		ans = min(ans, c)
	print(ans)
main()


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())
prim = [0] * (x + 1)
for n in range(2, x + 1):
	if not prim[n]:
		for k in range(2 * n, x + 1, n):
			prim[k] = n
p = prim[x]
res = 1000000000.0
for n in range(x - p + 1, x + 1):
	cur = n
	mxp = prim[cur]
	d = cur - mxp + 1
	res = min(res, d)
print(res)


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)


TN = 1

def resheto(l, k, n):
	i = 0
	while i < len(l):
		if l[i] % k == 0:
			l = l[:i] + l[i + 1:]
		i += 1
	lst = []
	for i in l:
		if n % i == 0:
			lst.append(i)
	return lst

def solution():
	x2 = int(input())
	n = 1000001
	max_prime = [0] * n
	s = list(range(n))
	s[1] = 0
	for i in s:
		if i > 1 and s[i]:
			for j in range(2 * i, n, i):
				s[j] = 0
				max_prime[j] = i
	min_x0 = n
	for x in range(x2 - max_prime[x2] + 1, x2 + 1):
		max_div = max_prime[x]
		tmp = x - max_div + 1
		if max_div and tmp < min_x0:
			min_x0 = tmp
	print(min_x0)
while TN != 0:
	solution()
	TN -= 1


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


from math import sqrt
import sys

def largest_prime_factor(n):
	for i in range(2, int(sqrt(n) + 1)):
		if n % i == 0:
			return largest_prime_factor(n // i)
	return n
x2 = int(input())
p2 = largest_prime_factor(x2)
m = sys.maxsize
for x1 in range(x2 - p2 + 1, x2 + 1):
	p1 = largest_prime_factor(x1)
	if p1 != x1 and m > x1 - p1 + 1:
		m = x1 - p1 + 1
print(m)


import math
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree1:

	def __init__(self, data, default=9999999, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] > k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater

def SieveOfEratosthenes(n):
	ans = []
	prime = [-9999999999 for i in range(n + 1)]
	p = 2
	while p <= n:
		if prime[p] == -9999999999:
			for i in range(p * 2, n + 1, p):
				prime[i] = p
		p += 1
	prime = [i - prime[i] + 1 for i in range(n + 1)]
	return prime
n = int(input())
prime = SieveOfEratosthenes(n)
ans = min(prime[prime[n]:n])
if ans > 10 ** 6:
	ans -= 9999999999 + 1
print(ans)


def testPrimal(n):
	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])
	return result
n = int(input())
print(testPrimal(n))


from math import floor, sqrt
import bisect
import math

def rwh_primes2(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)
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)


import math

def max_prime_factor(n):
	cur = 2
	while n != 1:
		while n % cur == 0:
			n = n // cur
		if n == 1:
			break
		cur += 1
		if cur > math.sqrt(n):
			return n
	return cur
X2 = int(input().strip())
p1 = max_prime_factor(X2)
res = float('inf')
for X1 in range(X2 - p1 + 1, X2 + 1):
	if p1 >= X1:
		continue
	p2 = max_prime_factor(X1)
	if X1 - p2 + 1 > p2:
		res = min(res, X1 - p2 + 1)
print(res)


lectura = int(input())
lista0 = [0] * (lectura + 1)
for i in range(2, lectura + 1):
	if lista0[i] == 0:
		for j in range(2 * i, lectura + 1, i):
			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)


def max_less_prime_divisor(n):
	(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)


a = []
for i in range(1000005):
	a.append(0)
n = int(input())
ans = n
for i in range(2, n + 1):
	if not a[i]:
		j = 2 * i
		while j <= n:
			a[j] = i
			j += i
	a[i] = i - a[i] + 1
for i in range(a[n], n + 1):
	ans = min(ans, a[i])
print(ans)


N = int(input())
P = [0 for _ in range(1000010)]
for i in range(2, N):
	if P[i] == 0:
		for j in range(2 * i, N + 1, i):
			P[j] = i
ans = 1000010
for i in range(N - P[N] + 1, N + 1):
	ans = min(ans, i - P[i] + 1)
print(ans)


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)


def getPrimes(n):
	primes = [0 for _ in range(n + 1)]
	for i in range(2, n + 1):
		if not primes[i]:
			for j in range(2 * i, n + 1, i):
				primes[j] = i
		primes[i] = i - primes[i] + 1
	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)


import math, sys, bisect, heapq
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
int1 = lambda x: int(x) - 1
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda : map(int, input().split())
alele = lambda : list(map(int, input().split()))
ilelec = lambda : map(int1, input().split())
alelec = lambda : list(map(int1, input().split()))

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])
N = int(input())
P = [0 for _ in range(1000010)]
for i in range(2, N):
	if P[i] == 0:
		for j in range(2 * i, N + 1, i):
			P[j] = i
ans = 1000010
for i in range(N - P[N] + 1, N + 1):
	ans = min(ans, i - P[i] + 1)
print(ans)


a = int(input())
b = [0 for i in range(a + 1)]
for i in range(2, a + 1):
	if b[i] == 0:
		for j in range(i + i, a + 1, i):
			b[j] = i
	b[i] = i - b[i] + 1
prim = a
for i in range(b[a], a + 1):
	prim = prim if prim < b[i] else b[i]
print(prim)


def factorize(n):
	res = []
	if n % 2 == 0:
		power = 0
		while n % 2 == 0:
			power += 1
			n //= 2
		res.append((2, power))
	i = 3
	while i * i <= n:
		if n % i == 0:
			power = 0
			while n % i == 0:
				power += 1
				n //= i
			res.append((i, power))
		i += 2
	if n > 1:
		res.append((n, 1))
	return res
x2 = int(input())
p = max((k for (k, _) in factorize(x2)))
k = x2 // p
res = float('inf')
for x1 in range(p * (k - 1) + 1, p * k + 1):
	p = max((k for (k, _) in factorize(x1)))
	k = x1 // p
	if k > 1:
		res = min(res, p * k - p + 1)
		if res < x1 // 2:
			break
print(res)


u = []
z = float('inf')
for x in range(1, 1000009):
	u.append(False)
n = int(input())
for x in range(2, n):
	if not u[x]:
		for y in range(2 * x, n + 1, x):
			u[y] = x
for x in range(n - u[n] + 1, n + 1):
	z = min(z, x - u[x] + 1)
print(z)


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)


x = int(input())
lp = [0 for x in range(x + 1)]
for i in range(2, x + 1):
	if lp[i] == 0:
		for j in range(i * 2, x + 1, i):
			lp[j] = i
	lp[i] = i - lp[i] + 1
p = x
for i in range(lp[x], x + 1):
	p = min(p, lp[i])
print(p)


def prime_factors(n):
	f = 2
	while f * f <= n:
		while n % f == 0:
			yield f
			n //= f
		f += 1
	if n > 1:
		yield n
x2 = int(input())
ans = x2
for x1 in range(x2 - max([x for x in prime_factors(x2)]) + 1, x2 + 1):
	tmp = x1 - max([x for x in prime_factors(x1)]) + 1
	if tmp >= 3:
		ans = min(ans, tmp)
	if ans < x1 // 2:
		break
print(ans)


p = int(input())
f = [0] * (p + 1)
for i in range(2, p + 1):
	if not f[i]:
		for j in range(2 * i, p + 1, i):
			f[j] = i
ans = p
for i in range(p - f[p] + 1, p + 1):
	ans = min(i - f[i] + 1, ans)
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
	return min_x0
x2 = int(input().strip())
get_primes()
print(algo(x2))


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)


x2 = int(input())
n = x2
vis = [False for i in range(n + 1)]
f = [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
			f[j] = i
ans = x2
for i in range(x2 - f[x2] + 1, x2 + 1):
	ans = min(ans, i - f[i] + 1)
print(ans)


n = int(input())
e = [0 for i in range(n + 1)]
for i in range(2, n + 1):
	if e[i] == 0:
		for j in range(i + i, n + 1, i):
			e[j] = i
	e[i] = i - e[i] + 1
ans = n
for i in range(e[n], n + 1):
	ans = ans if ans < e[i] else e[i]
print(ans)


x2 = int(input())

def maxPrimeDevisor(v):
	result = 0
	while v % 2 == 0:
		result = 2
		v //= 2
	i = 3
	while i * i <= v:
		if v % i == 0:
			while v % i == 0:
				v //= i
			result = max(result, i)
		else:
			i += 2
	if v > 1:
		result = max(result, v)
	return result
x1 = [max(3, x2 - maxPrimeDevisor(x2) + 1), x2]
x0 = x1[1]
for i in range(x1[0], x1[1] + 1):
	mpd = maxPrimeDevisor(i)
	if mpd != i:
		x0 = max(3, min(x0, i - maxPrimeDevisor(i) + 1))
print(x0)


numero = int(input())
lista = [0] * (numero + 1)
for i in range(2, numero + 1):
	if lista[i] == 0:
		for j in range(2 * i, numero + 1, i):
			lista[j] = i
	lista[i] = i - lista[i] + 1
p = numero
for i in range(lista[numero], numero + 1):
	p = min(p, lista[i])
print(p)


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)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def lpf(n, m=0, i=2):
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
	return m - n
x = int(input())
a = x
for i in range(lpf(x, x + 1), x + 1):
	if lpf(i, i + 1) >= 3:
		a = min(lpf(i, i + 1), a)
print(a)


def find_max_p(k):
	cur_k = k
	max_d = int(k ** 0.5) + 2
	d = 2
	max_p = 1
	while cur_k > 1 and d < max_d:
		while cur_k % d == 0:
			cur_k //= d
			max_p = d
		d += 1
	if cur_k > 1:
		return cur_k
	else:
		return max_p

def min_x(x):
	res = x - find_max_p(x) + 1
	if res > 1:
		return res
	else:
		return x
x_2 = int(input())
print(min([min_x(x_1) for x_1 in range(min_x(x_2), min(x_2, min_x(x_2) + 100))]))