迈克的村庄传来坏消息,一些小偷从当地工厂偷走了一堆巧克力!可怕!
除了喜欢甜食之外,这个地区的盗贼还非常贪婪。因此,当一个小偷拿走了自己的巧克力数量后,下一个小偷将比前一个小偷多拿走 k 倍。 k 的值(k > 1)是一个只有他们自己知道的秘密整数。还已知每个小偷的包最多可容纳 n 块巧克力(如果他们打算拿更多,则交易被取消),并且涉及的小偷正好有 4 个。
可悲的是,只有小偷知道 n 的值,但有传言说他们可以拿走巧克力的方式(对于固定的 n,但不固定的 k)是 m。如果其中一个小偷(他们应该按照拿走巧克力的顺序编号)拿走了不同数量的巧克力,则两种方式被认为是不同的。
迈克想要追踪小偷,所以他想知道他们的包是什么,n 的值将帮助他做到这一点。请找出n的最小可能值,或者告诉他谣言是假的,不存在这样的n。
输入
单行输入包含整数 m (1 ≤ m ≤ 1015) - 正如谣言所述,小偷可能偷巧克力的方式数。
输出
打印唯一的整数n——小偷的袋子可以携带的巧克力的最大数量。如果满足谣言的n个以上,则打印最小的一个。
如果对于虚假传闻的 m 不存在这样的 n,则打印 - 1。
示例
输入 #1
1
输出 #1
8
输入 #2
8
输出 #2
54
输入 #3
10
输出 #3
-1
注意
在第一个示例中,导致一种窃取巧克力的方式的最小 n 是 n = 8,而被盗巧克力的数量为 (1, 2, 4, 8)(每个小偷偷走的巧克力数量)。
在第二个示例中,恰好导致 8 条路的最小 n 是 n = 54,其可能性为: (1, 2, 4, 8), (1, 3, 9, 27), (2, 4, 8, 16), (2, 6, 18, 54), (3, 6, 12, 24), (4, 8, 16, 32), (5, 10, 20, 40), (6, 12, 24, 48)。
在第三个示例案例中,不存在恰好 10 种偷巧克力的方法。