17991번 - Carryless Square Root 다국어

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 k^th 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.

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

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