“该死！”查尔斯咒骂道。“我引擎里的这个笨拙的进位杆坏了！我刚才试着计算一个数的平方，但结果错了；所有的进位都丢失了。”

“嗯，”艾达沉思道，“没有进位的算术！我想知道我是否能根据我在引擎上看到的结果，推算出你最初的输入。”

无进位加法，记作 $\oplus$，与普通加法相同，只是忽略了所有进位（在十进制下）。因此，$37 \oplus 48$ 的结果是 $75$，而不是 $85$。

无进位乘法，记作 $\otimes$，使用小学乘法算法逐列进行，但中间的加法使用无进位加法计算。更正式地说，设 $a_m a_{m-1} \dots a_1 a_0$ 为 $a$ 的数字，其中 $a_0$ 是最低位。同样定义 $b_n b_{n-1} \dots b_1 b_0$ 为 $b$ 的数字。$c = a \otimes b$ 的数字由以下方程给出：

$$c_k = a_0 b_k \oplus a_1 b_{k-1} \oplus \dots \oplus a_{k-1} b_1 \oplus a_k b_0$$

其中，如果 $i > m$ 或 $j > n$，则任何 $a_i$ 或 $b_j$ 都被视为零。例如，$9 \otimes 1\,234$ 是 $9\,876$，$90 \otimes 1\,234$ 是 $98\,760$，而 $99 \otimes 1\,234$ 是 $97\,536$。

给定 $N$，求最小的正整数 $a$，使得 $a \otimes a = N$。

输入格式

输入包含一行，为一个整数 $N$，最多有 $25$ 位数字，且没有前导零。

输出格式

在一行中输出最小的正整数 $a$，使得 $a \otimes a = N$。如果不存在这样的 $a$，则输出 -1。

样例

样例输入 1

6

样例输出 1

4

样例输入 2

149

样例输出 2

17

样例输入 3

123476544

样例输出 3

11112

样例输入 4

15

样例输出 4

-1

Figure 1. A Cam from a Babbage Analytical Engine