Hide

Problem E
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