3336. Beautiful Numbers

单点时限: 2.0 sec

内存限制: 256 MB

We consider a number to be beautiful if it consists only of the digit 1 repeated one or more times. Not all numbers are beautiful, but we can make any base 10 positive integer beautiful by writing it in another base.

Given an integer $N$, can you find a base $B$ (with $B > 1$) to write it in such that all of its digits become 1? If there are multiple bases that satisfy this property, choose the one that maximizes the number of 1 digits.

输入格式

One line with an integer $N$ $(3 \leq N \leq 10^{18})$.

输出格式

Output the answer.

样例

Input
3
Output
2
Input
13
Output
3

提示

In case #1, the optimal solution is to write 3 as 11 in base 2.

In case #2, the optimal solution is to write 13 as 111 in base 3. Note that we could also write 13 as 11 in base 12, but neither of those representations has as many 1s.

25 人解决,47 人已尝试。

67 份提交通过,共有 647 份提交。

6.0 EMB 奖励。

创建: 7 年,1 月前.

修改: 7 年前.

最后提交: 1 年前.

来源: Kickstart Practice Round 2 2017

题目标签