A. Простой спорт
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб начинают свой день с простой игры. Они выбирают начальное целое число X0 ≥ 3 и пробуют достичь одного миллиона, играя по правилам, описанным ниже.

Первой ходит Алиса, затем игроки ходят по очереди. На i-м ходу игрок выбирает простое число, меньшее, чем текущее число, и увеличивает текущее число до наименьшего числа, кратного выбранному.

Формально, игрок выбирает простое число p < Xi - 1 и находит минимальное целое число Xi ≥ Xi - 1 такое, что p делит Xi нацело. Обратите внимание, если выбранное простое число p делит нацело число Xi - 1, то текущее число не меняется.

Ева увидела состояние игры после двух ходов. По данному X2 определите минимально возможное начальное число X0. Обратите внимание, игроки не обязательно играют оптимально. Вам нужно рассмотреть все возможные варианты хода игры.

Входные данные

Единственная строка содержит одно целое число X2 (4 ≤ X2 ≤ 106). Гарантируется, что число X2 составное, то есть не простое.

Выходные данные

Выведите одно целое число — минимально возможное начальное число X0.

Примеры
Входные данные
14
Выходные данные
6
Входные данные
20
Выходные данные
15
Входные данные
8192
Выходные данные
8191
Примечание

В первом примере минимальное начальное число равно X0 = 6. Например, возможна следующая игра:

  • Алиса выбирает простое число 5 и получает X1 = 10,
  • Боб выбирает простое число 7 и получает X2 = 14.

Во втором примере минимально возможное X0 = 15.

  • Алиса выбирает простое число 2 и получает X1 = 16,
  • Боб выбирает простое число 5 и получает X2 = 20.