当前没有测试数据。

题目描述

神秘的古老文明中，人们相信数字具有神秘的力量和意义。

他们相信每个数字都有一个特殊的进制，被称为 “神” 进制。“神” 进制被视为神圣的代表，能够揭示数字的真正本质。

如果 n 的k(k≥2) 进制数的所有数位全为 1 ，则称 k(k≥2) 是 n 的一个 “神” 进制，即满足： $k^0$+$k^1$+$k^2$+$k^3$+...+$k^x$=n。

你的任务是寻找一个给定的数字 n 的最小 "神" 进制，以揭示其神秘的含义。

输入

一个字符串 n，表示一个十进制数。

输出

一个字符串，表示 n 的最小 "神" 进制 k。

样例

输入复制

13

输出复制

3

输入复制

4681

输出复制

8

输入复制

1000000000000000000

输出复制

999999999999999999

说明

【样例 1 解释】

13 的 3 进制是 111。

13 的 12 进制是 11。

由于 3 进制数 111 是满足题意的最小值，所以输出 3 。

【样例 2 解释】

4681 的 8 进制是 11111 ，是符合题意的最小值，所以输出 8。

【样例 3 解释】

1000000000000000000 的 999999999999999999 进制是 11 ，是符合题意的最小值，所以输出 999999999999999999。

【数据范围】

30% 的数据满足：3≤n≤1$0^3$。 60% 的数据满足: 3≤n≤1$0^9$。 100% 的数据满足: 3≤n≤1$0^{18}$。