Problem Description

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

Input Format

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

Output Format

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

22

8

Hint

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