该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

Kevin 在数学课上刚刚学完了进制转换，老师留下了一个有趣的挑战：“每个数字在不同进制下会呈现不同的模样，有的甚至会左右对称，形成回文数。”

放学后，Kevin 拿出自己最喜欢的数字——从幸运饼干里得到的十进制数 $n$（$1 \le n \le 10^{12}$）。他想知道：在 $2$ 到 $16$ 的进制中，哪一种进制能让这个数字变成回文？而且，他只要最小的那个进制。

Kevin 试着把 $n=5$ 转成二进制，得到 101 —— 哇，左右一样！他开心地记下 $B=2$。接着他试了 $n=10$，二进制 1010 不对称，三进制 101 却对称了，所以答案是 $3$。可是对于 $n=114514$，他翻遍 $2$ 到 $16$ 进制，没有任何一种能让它变成回文，只能无奈地写下 -1。

现在，Kevin 把他的数字交给你，请你帮他编写一个程序，快速找到那个最小的回文进制 $B$。你能帮 Kevin 解决这个问题吗？

输入格式

一行，一个整数 $n$。

输出格式

一行，一个整数 $B$ 或 -1。

样例

5

2

10

3