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 for some positive integer y

.

Input

The first line contains a single integer n

(1≤n≤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 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.

比赛的时候想着将数字看成字符串的,但是没有想清楚就写了,最后终测还是挂掉了.

看成字符串处理,可以不考虑前缀零.然后转换成数字判断是否满足条件即可

#include
    
     #define ll long long#define inf 0x3f3f3f3f#define pb push_back#define rep(i,a,b) for(int i=a;i
     
      =a;i--)using namespace std;const int N=2e5+100;ll arr[N];vector
      
        G;struct node{    string x;    int d;};int main(){    string str;    cin>>str;    node t={str,0};    map
       
        mp;    map
        
         mp1;    for(ll i=1;i<1e5;i++)    {        mp[i*i]=1;    }    queue
         
          q; q.push(t); mp1[str]=1; while(!q.empty()) { t=q.front(); q.pop(); string s=t.x; int sum=(int)s[0]-'0'; for(int i=1;i