Hide

# Problem ETilefni

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