奇妙的汽车

题目描述

你有着一辆奇妙的汽车,这辆汽车有着自动加速的功能。打个比方吧,第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。

输入输出样例

输入样例 #1

15121

输出样例 #1

-1

输入样例 #2

571

输出样例 #2

5

说明

数据规模 对于30%数据,有S<=100; 对于70%数据,有S<=107; 对于100%数据,有9