Make a Square

题意翻译

给定一个不含前导零的正整数 $n(1\le n\le 2\cdot 10^9)$，可以删除其中的一些位，使其变成一个另正整数 $x$。要求 $x$ 为完全平方数。求最小删除次数。若无解，输出 `-1`。 Translated by @我谔谔

题目描述

You are given a positive integer $ n $ , written without leading zeroes (for example, the number 04 is incorrect). In one operation you can delete any digit of the given integer so that the result remains a positive integer without leading zeros. Determine the minimum number of operations that you need to consistently apply to the given integer $ n $ to make from it the square of some positive integer or report that it is impossible. An integer $ x $ is the square of some positive integer if and only if $ x=y^2 $ for some positive integer $ y $ .

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^{9} $ ). The number is given without leading zeroes.

输出格式

If it is impossible to make the square of some positive integer from $ n $ , print -1. In the other case, print the minimal number of operations required to do it.

输入输出样例

输入样例 #1

8314

输出样例 #1

2

输入样例 #2

625

输出样例 #2

0

输入样例 #3

333

输出样例 #3

-1

说明

In the first example we should delete from $ 8314 $ the digits $ 3 $ and $ 4 $ . After that $ 8314 $ become equals to $ 81 $ , which is the square of the integer $ 9 $ . In the second example the given $ 625 $ is the square of the integer $ 25 $ , so you should not delete anything. In the third example it is impossible to make the square from $ 333 $ , so the answer is -1.