## Algorithm

C. Make a Square
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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=y2�=�2 for some positive integer y.

Input

The first line contains a single integer n (1n21091≤�≤2⋅109). The number is given without leading zeroes.

Output

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.

Examples
input
Copy
8314
output
Copy
2
input
Copy
625
output
Copy
0
input
Copy
333
output
Copy
-1
Note

In the first example we should delete from 83148314 the digits 33 and 44. After that 83148314 become equals to 8181, which is the square of the integer 99.

In the second example the given 625625 is the square of the integer 2525, so you should not delete anything.

In the third example it is impossible to make the square from 333333, so the answer is -1.

## Code Examples

### #1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int n, all[15], len;
long long s[1000000];

int rec(int idx, long long num, bool tak, int cnt) {
if(idx == len) {
if(tak && s[int(sqrt(num))] == num)
return len - cnt;
return 1e9;
}

if(all[idx] == 0 && !tak)
return rec(idx + 1, num, tak, cnt);

return min(rec(idx + 1, num, tak, cnt), rec(idx + 1, num * 10 + all[idx], true, cnt + 1));
}

int main() {
for(int i = 0; i < 1000000; ++i)
s[i] = 1ll * i * i;

cin >> n;

len = log10(n) + 1;
for(int i = len - 1; i >= 0; --i) {
all[i] = n % 10;
n /= 10;
}

int res = rec(0, 0, false, 0);

if(res == 1e9)
cout << -1 << endl;
else
cout << res << endl;

return 0;
}
Copy The Code &

Input

cmd
8314

Output

cmd
2