시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 512 MB 2 2 2 100.000%

문제

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 ck 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 aa = n in carryless multiplication.

입력

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

출력

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

예제 입력 1

6

예제 출력 1

4

예제 입력 2

149

예제 출력 2

17

예제 입력 3

123476544

예제 출력 3

11112

예제 입력 4

15

예제 출력 4

-1