Description

kkk made a sequence consisting entirely of positive integers. Don’t think it’s anything magical — it’s just $1, 2, …, n$, and $n$ is given. kkk’s classmate lzn thinks $0$ is a nice number (it looks very round), so when kkk wasn’t around, he cleverly changed the whole sequence into $0$ (well, he was just getting ready to do so).

But kkk suddenly came back! lzn’s plan failed. Unwilling to give up, he told kkk: each time, I can select some numbers from this sequence and subtract the same positive integer from all of them. After a finite number of such operations, the entire sequence can become $0$.

kkk didn’t believe it, so lzn calculated the minimum number of such operations needed to make the entire sequence become $0$.

Input Format

A positive integer $n$.

Output Format

Output the minimum number of operations. If there is no solution, output -1.

2

2

Hint

Constraints

For all testdata, $1 \le n \le 10^9$.

Translated by ChatGPT 5