Numeral System Base#6318
Given a natural number , find the smallest base of a numeral system such that can be represented as a one followed by zeros in this system (that is, N = K^m for some m \geq 1).
In other words, find the smallest such that when is written in base , it has the form .
The input consists of a single line containing a natural number (2 \leq N \leq 10^9).
The output should be a single line containing one natural number – the smallest base of the numeral system in which is represented as .
Example 1