New Maths

“Drat!” cursed Charles. “This stupid carry bar is not working in my Engine! I just tried to calculate the square of a number, but it’s wrong; all of the carries are lost.”

“Hmm,” mused Ada, “arithmetic without carries! I wonder if I can figure out what your original input was, based on the result I see on the Engine.”

*Carryless addition*, denoted by $\oplus $, is the same as normal
addition, except any carries are ignored (in base $10$). Thus, $37 \oplus 48$ is $75$, not $85$.

*Carryless multiplication*, denoted by $\otimes $, is performed using the
schoolboy algorithm for multiplication, column by column, but
the intermediate additions are calculated using *carryless
addition*. More formally, Let $a_ m a_{m-1} \ldots a_1 a_0$ be the
digits of $a$, where
$a_0$ is its least
significant digit. Similarly define $b_ n b_{n-1} \ldots b_1 b_0$ be the
digits of $b$. The digits
of $c = a \otimes b$ are
given by the following equation:

where any $a_ i$ or $b_ j$ is considered zero if $i > m$ or $j > n$. For example, $9 \otimes 1\, 234$ is $9\, 876$, $90 \otimes 1\, 234$ is $98\, 760$, and $99 \otimes 1\, 234$ is $97\, 536$.

Given $N$, find the smallest positive integer $a$ such that $a \otimes a = N$.

The input consists of a single line with a positive integer $N$, with at most $25$ digits and no leading zeros.

Print, on a single line, the least positive number
$a$ such that $a \otimes a = N$. If there is no such
$a$, print ‘`-1`’ instead.

Sample Input 1 | Sample Output 1 |
---|---|

6 |
4 |

Sample Input 2 | Sample Output 2 |
---|---|

149 |
17 |

Sample Input 3 | Sample Output 3 |
---|---|

123476544 |
11112 |

Sample Input 4 | Sample Output 4 |
---|---|

15 |
-1 |