P8795 [Lanqiao Cup 2022 National A] Choosing Primes

Xiao Lan has a number $x$. In each operation, Xiao Lan chooses a prime $p$ that is less than $x$, then keeps increasing $x$ by $1$ until $x$ becomes a multiple of $p$ (if $x$ is already a multiple of $p$ at the beginning, then $x$ stays unchanged). Xiao Qiao saw the result $n$ obtained after Xiao Lan performed the above operation twice, and he wants to know what $x$ was at the beginning. If there are multiple possibilities, he wants to know the minimum possible initial value of $x$. If there is no solution, it means Xiao Qiao saw it wrong; in this case, output $-1$.

The input contains one line with an integer $n$, representing the value of $x$ after two operations.

Output one line with an integer representing the initial value of $x$. If there are multiple solutions, output the smallest one. If there is no solution, output $-1$.

**Constraints** - For $60\%$ of the testdata, $1 \leq n \leq 5000$. - For all testdata, $1 \leq n \leq 10^6$. Lanqiao Cup 2022 National Contest Group A Problem G. Translated by ChatGPT 5