Алиса и Боб начинают свой день с простой игры. Они выбирают начальное целое число X0 ≥ 3 и пробуют достичь одного миллиона, играя по правилам, описанным ниже.
Первой ходит Алиса, затем игроки ходят по очереди. На i-м ходу игрок выбирает простое число, меньшее, чем текущее число, и увеличивает текущее число до наименьшего числа, кратного выбранному.
Формально, игрок выбирает простое число p < Xi - 1 и находит минимальное целое число Xi ≥ Xi - 1 такое, что p делит Xi нацело. Обратите внимание, если выбранное простое число p делит нацело число Xi - 1, то текущее число не меняется.
Ева увидела состояние игры после двух ходов. По данному X2 определите минимально возможное начальное число X0. Обратите внимание, игроки не обязательно играют оптимально. Вам нужно рассмотреть все возможные варианты хода игры.
Примечание
В первом примере минимальное начальное число равно X0 = 6. Например, возможна следующая игра:
- Алиса выбирает простое число 5 и получает X1 = 10,
- Боб выбирает простое число 7 и получает X2 = 14.
Во втором примере минимально возможное X0 = 15.
- Алиса выбирает простое число 2 и получает X1 = 16,
- Боб выбирает простое число 5 и получает X2 = 20.