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$.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^{9}$). 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
8314

Output
2

Input
625

Output
0

Input
333

Output
-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.

Difficulty: interview

Starter code:

Solutions:
ar=[]
for i in range(1,10**5):
    if(i*i>2*10**9):break
    ar.append(i*i)
s=input()
ans=len(s)
for x in ar:
    s2=str(x)
    i=0
    for x in range(len(s)):
        if i<len(s2) and s[x]==s2[i]:
            i+=1
    if(i==len(s2)):
        ans=min(ans,len(s)-i)
if(ans==len(s)):
    print(-1)
else:
    print(ans)

def main():
    squares = set(str(x * x) for x in range(100000))
    s = input()
    n = len(s)
    ans = float('inf')
    for mask in range(1, (1 << n)):
        o = ''.join([s[i] for i in range(n) if mask & (1 << i) > 0])
        if o[0] == '0':
            continue
        if o in squares:
            pc = bin(mask).count('1')
            ans = min(ans, n - pc)

    if ans == float('inf'):
        ans = -1
    print(ans)

main()


n = input()
l = len(n)
res = 1000000
for x in range(1, 2 ** l):
    g = x
    s = ''
    i = 0
    while g:
        if g % 2:
            s += n[i]
        g //= 2
        i += 1
    if s.startswith('0'):
        continue
    h = int(s)
    sq = h ** 0.5
    if sq == int(sq):
        res = min(res, l - len(s))
print(res if res != 1000000 else -1)


n = input()
k = len(n)
ans = 100
for i in range(2 ** k):
    s = bin(i)[2:]
    s = '0' * (k - len(s)) + s
    sq = ''
    for j in range(k):
        if s[j] == '1':
            sq += n[j]
    if sq == '' or sq[0] == '0':
        continue
    sq = int(sq)
    l = 0
    r = 1000000
    while r - l > 1:
        c = (r + l) // 2
        if c * c > sq:
            r = c
        else:
            l = c
    if l * l == sq:
        ans = min(ans, s.count('0'))
if ans == 100:
    print(-1)
else:
    print(ans)


def is_sqr(x):
  y = 1
  while y**2 < x:
    y += 1
  return y**2 == x

from itertools import combinations
n = input()
ans = 100
for r in range(1, len(n) + 1):
  for item in combinations(n, r):
    #print(int(''.join(item)))
    if is_sqr(int(''.join(item))) and item[0] != '0':
      ans = min(ans, len(n) - len(item))
print(ans if ans != 100 else -1)


def valid_int(n):
    return int(round(n ** 0.5)) ** 2 == n

def valid(s):
    return valid_int(int(s))

def no_start_zero(s):
    return s[0] != '0'

n = input()

def adj(s):
    if len(s) <= 1: return []
    for i in range(len(s)):
        ss = s[:i] + s[i+1:]
        if no_start_zero(ss):
            yield ss

q = [n]
seen = set()

while q:
    node = q.pop(0)
    if valid(node):
        print(len(n) - len(node))
        return
    for child in adj(node):
        if child not in seen:
            seen.add(child)
            q.append(child)
print(-1)

import atexit
import io
import sys
import math

# Buffering IO
_INPUT_LINES = sys.stdin.read().splitlines()
input = iter(_INPUT_LINES).__next__
_OUTPUT_BUFFER = io.StringIO()
sys.stdout = _OUTPUT_BUFFER

@atexit.register
def write():
    sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
    

def main():
    n = input()
    mm = 0
    for i in range(1, 2**len(n)):
        x = ''
        for c in range(len(n)):
            if i%2:
                x += n[c]
            i = i//2
         
        if x[0] == '0':
            continue
        xx = int(x) 
        if int(xx ** .5) ** 2 == xx:
            if len(x)>mm:
                mm = len(x)
    print(len(n) - mm if mm>0 else -1)
    
def __starting_point():
    main()

__starting_point()

def check(t, s):
    cur_t = 0
    for j in range(len(s)):
        while cur_t < len(t) and t[cur_t] != s[j]:
            cur_t += 1
        if cur_t == len(t):
            return False
        cur_t += 1
    return True


s1 = input()
for i in range(45 * 1000, 0, -1):
    s2 = str(i * i)
    if check(s1, s2):
        print(len(s1) - len(s2))
        return
print(-1)

import itertools


def try_sqrt(n):
    m = int(n**.5)
    return True if abs(m*m - n) < 1e-6 else False


N = int(input())
if try_sqrt(N):
    print(0)
    quit()

L = list(str(N))
for i in reversed(range(1, len(L))):
    for num_l in itertools.combinations(L, i):
        if num_l[0] == "0":
            continue
        num = int("".join(num_l))
        if try_sqrt(num):
            print(len(L)-i)
            quit()

print(-1)

a = int(input())
sa = str(a)
i = 1

def check(sa, si):
    cc = 0
    for i in range(len(sa)):
        if sa[i] == si[cc]:
            cc += 1
        if cc == len(si):
            break
    if cc == len(si):
        return True
    else:
        return False
i = int(a ** 0.5 + 1)
while i > 0:
    if i * i > a:
        i -= 1
        continue
    si = str(i * i)
    T = check(sa, si)
    if T:
        print(len(sa) - len(si))
        quit()
    i -= 1
print(-1)


import sys
import math
from functools import lru_cache
 
@lru_cache(maxsize = None)
def solution(nstr, nint, acc):
    msf = float('inf')
    if (math.sqrt(nint) - int(math.sqrt(nint))) == 0.0:
        return acc
    for i in range(len(nstr)):
        mstr = nstr[:i] + nstr[i+1:]
        if mstr:
            if mstr[0] == '0':
                continue
            msf = min(msf, solution(mstr,int(mstr),acc+1))
    if msf == float('inf'):
        return float('inf')
    return msf

n = sys.stdin.readline().strip()

res = solution(n, int(n) ,0)
if res == float('inf'):
    print(-1)
else:
    print(res)

def lcs(X , Y):
    # find the length of the strings
    m = len(X)
    n = len(Y)
 
    # declaring the array for storing the dp values
    L = [[None]*(n+1) for i in range(m+1)]

    for i in range(m+1):
        for j in range(n+1):
            if i == 0 or j == 0 :
                L[i][j] = 0
            elif X[i-1] == Y[j-1]:
                L[i][j] = L[i-1][j-1]+1
            else:
                L[i][j] = max(L[i-1][j] , L[i][j-1])
 
    # L[m][n] contains the length of LCS of X[0..n-1] & Y[0..m-1]
    return L[m][n]
x=input()
import math
ans=0
for i in range(int(math.sqrt(int(x))),0,-1):
    if(lcs(x,str(i*i))==len(str(i*i))):
        ans=len(str(i*i))
        break
if(ans):
    print(len(x)-ans)
else:
    print(-1)







n=input()
ps=[]
for i in range(44722):
    ps.append(str(i*i))
ans=20
for i in range(1,44722):
    k=0
    l=len(ps[i])
    for j in n:
        if j==ps[i][k]:
            k+=1
        if k==l:
            break
    if k==l:
        ans=min(ans,len(n)-l)
if ans==20:
    ans=-1
print(ans)


n = input()
a=[]
for i in range(1,int((2*10**9)**0.5)+1):
    a.append(i**2)
m = float('inf')
l = len(n)
for i in range(1,2**len(n)):
    bi = bin(i)[2:]
    bi = '0'*(l-len(bi))+bi
    ne = ''
    for i in range(l):
        if bi[i] == '1':
            ne += n[i]
    if ne[0] == '0':continue
    else:
        if int(ne) in a:
            m = min(m,bi.count('0'))
if m == float('inf'):print(-1)
else:print(m)


from math import *

strN = input()
n = int(strN)

def IsMatch(t):
    strT = str(t)
    if len(strN) == len(strT):
        if n == t: return 0
        else: return -1
    p = 0
    for c in strT:
        p = strN.find(c, p)
        if p == -1:
            break
        else:
            p += 1
    if p == -1:
        return -1
    else:
        return len(strN) - len(strT)

N = floor(sqrt(n))
for i in range(N, 0, -1):
    t = i*i
    d = IsMatch(t)
    if d >= 0:
        print(d)
        return
print(-1)


n=input()
le=len(n)
m=le
for i in range(1,2**le):
    i=bin(i)[2:]
    s=''
    c=le
    for j in range(len(i)):
        if i[-1-j]=='1':
            s=n[le-1-j]+s
            c-=1
    if s[0]=='0':
        continue
    s=int(s)
    if int(s**(1/2))**2==s:
        m=min(m,c)
if m==le:
    print(-1)
else:
    print(m)


import math

def read_data():
    n = int(input().strip())
    return n

def compare(s):
    mpos = 0
    spos = 0
    count = 0
    while spos < len(s):
        npos = m.find(s[spos],mpos)
        if npos == -1:
            return -1
        count += npos - mpos
        mpos = npos + 1
        spos += 1
    count += len(m) - mpos
    return count

def solve():
    start = int(math.sqrt(n))
    for i in range(start,0,-1):
        c = compare(str(i*i))
        if c > -1:
            return c
    return -1

n = read_data()
m = str(n)
print(solve())

def is_perfect_square(n):
        return round(n ** 0.5) ** 2 == n


from itertools import combinations
s = input()
ls = len(s)
sl = [i for i in s]
x = []
for i in range(1,len(s)+1):
    comb = combinations(sl,i)
    for j in list(comb):
        x.append(list(j))
y = []
for i in x:
    a = ''
    for j in i:
        a+=j
    y.append(int(a))
y = list(set(y))
y.sort(reverse=True)
#print(y)
f = 0
for i in y:
    if(i!=0):
        if is_perfect_square(i):
            #print(i)
            f = 1
            break
if(f):
    print(ls-len(str(i)))
else:
    print(-1)

n = int(input())

s = str(n)
lst = []
t = set()
def xxx(string):
    if string[0] == '0':
        return
    x = int(string)
    
    
    if x in t:
        return
    t.add(x)
    
    k1 = 0
    k2 = 10 ** 6
    while k2 - k1 != 1:
        k = (k1 + k2) // 2
        if k ** 2 <= x:
            k1 = k
        else:
            k2 = k
    if k1 ** 2 == x:
        lst.append(len(str(x)))

    if len(string) == 1:
        return
    for x in range(len(string)):
        xxx(string[:x] + string[x + 1:])
    return

xxx(s)
if len(lst) == 0:
    print(-1)
else:
    print(len(s) - max(lst))


from math import sqrt, floor

n = input()

def is_square(n):
    f = floor(sqrt(n))
    return f*f == n or (f+1)*(f+1) == n


def min_to_square(d, n):
    if len(n) == 1:
        return d if is_square(int(n)) else 100

    if n[0] == '0':
        return 100

    if (n[0] != '0' and is_square(int(n))) or n == '0':
        return d

    m = min([min_to_square(d + 1, n[:i] + n[i + 1:]) for i in range(len(n))])

    return m

def mts(n):
    min_ = 100

    for i in range(1, 2**(len(n))):
        s = "{0:b}".format(i).zfill(len(n))

        newn = ''.join([n[i] for i in range(len(n)) if s[i] == '1'])

        if is_square(int(newn)) and newn[0] != '0':
            min_ = min(min_, sum(1 for c in s if c == '0'))

    return min_


print(mts(n) if mts(n) < 100 else -1)

import math


def nop(a, b):
    l = 0
    for i in range(len(a)):
        d = a[i]
        while l < len(b) and b[l] != d:
            l += 1
        if l >= len(b) and b[l - 1] != d:
            return 0
        elif l < len(b) and b[l] != d:
            return 0
        l += 1
        if i < len(a) - 1 and l >= len(b):
            return 0
    return 1

a = int(input())
b = int(math.sqrt(a))
c = []
k = b
for i in range(k):
    if nop(str(b ** 2), str(a)) == 1:
        c.append(len(str(a)) - len(str(b ** 2)))
    b -= 1
c.sort()
if len(c) > 0:
    print(c[0])
else:
    print(-1)

#!/usr/bin/env python3

from math import sqrt

import itertools

def issq(k):
	k = int(k)
	return k == int(sqrt(k)) ** 2

ns = input().strip()
l = len(ns)

def getsub(ns, it):
	return ''.join(ns[i] for i in it)

def findmin(ns):
	for i in range(l, 0, -1):
		for it in itertools.combinations(list(range(l)), i):
			its = getsub(ns, it)
			if its.startswith('0'):
				continue
			if issq(its):
				return l - i
	return -1

print(findmin(ns))