Carryless Square Root

Time limit1sMemory limit512 MB

Summary

Given an integer n, find the smallest positive integer a whose digit-wise convolution squares to n with all carries discarded, or report that none exists.

Level: Medium7 of 10
Topics: Math, Number theory, Brute force, Implementation
Solved: No attempts yet

Problem

Carryless addition is the same as normal addition, except any carries are ignored (in base 10). Thus, 37 + 48 is 75, not 85.

Carryless multiplication is performed using the schoolbook algorithm for multiplication, column by column, but the intermediate sums are calculated using carryless addition. Thus:

9 ∙ 1234 = 9000 + (900 + 900) + (90 + 90 + 90) + (9 + 9 + 9 + 9) = 9000 + 800 + 70 + 6 = 9876

90 ∙ 1234 = 98760

99 ∙ 1234 = 98760 + 9876 = 97536

Formally, define c_k to be the kth digit of the value c. If c = a · b then

[c_k = \left[ \sum_{i+j=k}{a_i \cdot b_j} \right] \mod 10]

Given an integer n, calculate the smallest positive integer a such that a ∙ a = n in carryless multiplication.

Input

The input consists of a single line with an integer n (1 ≤ n ≤ 10^25).

Output

Output the smallest positive integer that is a carryless square root of the input number, or −1 if no such number exists.

Examples4

Example 1
Input
```
6
```
Expected output
```
4
```
Example 2
Input
```
149
```
Expected output
```
17
```
Example 3
Input
```
123476544
```
Expected output
```
11112
```
Example 4
Input
```
15
```
Expected output
```
-1
```