Migrated from Lutece 1308 Banana Watch

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

As a famous technology company, Banana Inc. invents Banana Watch, redefining the watch.

While a normal watch has $12$ indexes and two or three moving hands, a Banana Watch has $n$ indexes and a moving hand.

The moving hand is at $0$ initially, and in $1^{st}$ second, it turns $1$ index clockwise; in $2^{nd}$ second, it turns $2$ indexes clockwise; ... ; in $i^{th}$ second, it turns $i$ indexes clockwise. When it moves back to $0$ exactly, one minute passes (Yes, Banana Inc. also redefines the minute).

How many seconds in the first minute?

Input

One integer $n$.

$3\leq n\leq 10^6$

Output

Print the number of seconds in the first minute.

Samples

3

2

5

4

Note

If $n=5$, in $1^{st}$ second, the hand moves to $1$; in $2^{nd}$ second, the hand moves to $3$; in $3^{rd}$ second, the hand moves to $1$; in $4^{th}$ second, the hand moves to $0$. So the answer for $n=5$ is $4$.

Resources

The 14th UESTC Programming Contest Final