Problem D
Tilefni
Languages
en
is
The University of Iceland has held many important birthdays. In $2011$, for example, it became a century old. The most important birthdays are those starting with a one followed by some number of zeros. The more zeros, the better. The problem with this is that there are few important birthdays. Your job is to choose a new base to make a birthday important. For example, this year there are $81$ years since the university moved to the current location. This is not an important birthday in base ten, but in base nine this becomes $100$ years which is important. It would be even better to use base three where it would be $10^4$ years.
Input
The input consists of a single integer $2 \leq n \leq 10^{18}$, the birthday that is being celebrated in base ten.
Output
Print the largest number of zeros that can be achieved by changing the base.
| Sample Input 1 | Sample Output 1 |
|---|---|
81 |
4 |
| Sample Input 2 | Sample Output 2 |
|---|---|
100 |
2 |
| Sample Input 3 | Sample Output 3 |
|---|---|
30 |
1 |
