2018 Yonsei University Programming Contest

After 2015, 2016 and 2017, the Yonsei University computer science programming contest is held again this year.

Dohyun was moved that the campus contest runs for a fourth year in a row, so he prepared a showy opening ceremony and was ready to pay for it himself.

What he wanted was fireworks. He thought everyone would love a firework that blows straight through the ceiling of lecture room A528. The firework he plans to order bursts like this.

1. The single large spark made by the launched firework reaches a suitable height and splits into $K$ medium sparks in one burst.
2. Each of the $K$ medium sparks splits again into $K$ small sparks and bursts.
3. After that every spark dies out.

Dohyun tried to find a suitable firework, but the seller would not tell him the value of $K$. The seller told him only the total number of sparks one firework makes, counting the first large spark together with all medium and small sparks. Dohyun never worked out which firework suited him, so he bought none.

He then promised one extra solved problem in this contest to any student who settles the question for him. To win the contest, take the total number of sparks a firework makes and find $K$.

The total number of sparks $N$ is given. ($3 \le N \le 10101$)

Print the value of $K$. This value is guaranteed to be an integer, and impossible cases are not given as input.