C. Prime Partition
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$N$$$ distinct integers, ranging from $$$1$$$ to $$$N$$$.

Your task is to split the numbers into two non-empty groups such that the absolute difference between the sums of the two groups is a prime number.

Among all possible valid partitions, you must determine the maximum possible prime that can be obtained as the difference of sums.

Input

The only line contains a single integer $$$N (2 \leq N \leq 10^6)$$$.

Output

Print the maximum possible prime. If no such partition exists, output $$$-1$$$.

Example
Input
4
Output
2
Note

The numbers are $$$[1, 2, 3, 4]$$$.

We must divide them into two non-empty groups such that the absolute difference between the sums of the two groups is a prime number.

Some valid groupings are:

$$$$$$ \text{Group 1: } [4],\quad \text{Group 2: } [1, 2, 3] \Rightarrow \text{Sums are } 4 \text{ and } 6 \Rightarrow \text{Difference} = |4 - 6| = 2\ (\text{prime})\ $$$$$$ $$$$$$ \text{Group 1: } [1, 3],\quad \text{Group 2: } [2, 4] \Rightarrow \text{Sums are } 4 \text{ and } 6 \Rightarrow \text{Difference} = |4 - 6| = 2\ (\text{prime})\ $$$$$$

Among all valid partitions, the maximum prime difference we can achieve is $$$2$$$.