Problem I
Cryptographic Keys
Lukáš invented a special cryptographic algorithm. He can not tell you the details, of course. However, there is one problem. He doesn’t know how to select strong keys for messages. Can you help him?
Suppose that a message is a positive integer $N$. The strongest key is an integer $K$ such that $N$ written in base $K$ has the most zeros at the end. In case of a tie, the smallest such $K$ is the strongest.
For example, the strongest key for $N = 72$ is $K = 2$, because $72 = 1001000_2$ ($72$ written in base $2$) has $3$ zeros at the end. Using base $3$, we only get $2$ zeroes at the end (because $72 = 2200_3$), using base $6$ would also give us $2$ zeros, and no other base would give us more than $1$ zero.
Input
Input contains one line with one integer $N$, $2 \le N \le 10^{12}$.
Output
Output contains one line with one integer $K$ such that $N$ written in base $K$ has the most zeros at the end and is the smallest $K$ with this property.
Sample Input 1 | Sample Output 1 |
---|---|
72 |
2 |