题目描述

你有着一辆奇妙的汽车，这辆汽车有着自动加速的功能。打个比方吧，第 $1$ 天你驾驶着它可以行驶 $a$ 路程，那么第 $2$ 天你可以让它所走的路程增加到第 $1$ 天的 $2$ 到 $9$ 倍（必须是其中一个整数），也就是 $2a$ 到 $9a$，第 $3$ 天它所行驶的路程就将达到第 $2$ 天的 $2$ 到 $9$ 倍……也就是说，这辆车在第 $i$ 天所走的路程一定是第 $i-1$ 天的 $2$ 到 $9$ 倍，而且还必须是它的整数倍。

现在你迫不及待地开着这辆车要从 $A$ 城市出发到 $B$ 城市旅游，顺便在路上展示一下这辆旷世奇车。你已经知道你需要行驶的里程 $S$，现在请你合理安排第 $1$ 天的里程和接下来每天需要增加路程的倍数，好让你能够在最短的天数内，恰好到达 $B$ 城市。

不过，因为你想要好好展示一下你的车，而且也是为了交通安全，你被要求至少要花 $2$ 天时间，如果不能找到这样的方案请输出 -1。

输入格式

一个正整数 $S$，代表 $A$ 城市到 $B$ 城市的里程。

输出格式

一个数，代表最少需要行驶的天数，如果无解输出 -1。

15121

-1

571

5

提示

数据规模

对于 $30\%$ 数据，有 $S\leq 100$；

对于 $70\%$ 数据，有 $S\leq 10^7$；

对于 $100\%$ 数据，有 $9<S\leq 10^8$。