You are given an integer $n$ from $1$ to $10^{18}$ without leading zeroes.

In one move you can swap any two adjacent digits in the given number in such a way that the resulting number will not contain leading zeroes. In other words, after each move the number you have cannot contain any leading zeroes.

What is the minimum number of moves you have to make to obtain a number that is divisible by $25$? Print -1 if it is impossible to obtain a number that is divisible by $25$.


-----Input-----

The first line contains an integer $n$ ($1 \le n \le 10^{18}$). It is guaranteed that the first (left) digit of the number $n$ is not a zero.


-----Output-----

If it is impossible to obtain a number that is divisible by $25$, print -1. Otherwise print the minimum number of moves required to obtain such number.

Note that you can swap only adjacent digits in the given number.


-----Examples-----
Input
5071

Output
4

Input
705

Output
1

Input
1241367

Output
-1



-----Note-----

In the first example one of the possible sequences of moves is 5071 $\rightarrow$ 5701 $\rightarrow$ 7501 $\rightarrow$ 7510 $\rightarrow$ 7150.

Difficulty: introductory

Starter code:

Solutions:
import sys
import queue

INFINITY = 10**10

def main():
    n = input()
    print(solve(n))


def solve(n):
    if int(n) < 1000:
        return brute(n)
        
    forward = min([calc(str(n), last_digits) for last_digits in ["00", "25", "50", "75"]])
    reverse = min([calc(str(n), last_digits) + 1 for last_digits in ["52", "05", "57"]])
    res = min(forward, reverse)
    
    if res >= INFINITY:
        res = -1
    
    return res


def calc(n, last_digits):
    if not last_digits:
        return 0
    
    idx = n.rfind(last_digits[-1])
    if idx == -1:
        return INFINITY
    
    res = len(n) - idx - 1
    n = n[:idx] + n[(idx+1):]
    last_digits = last_digits[:-1]
    
    extra = 0
    if n and n[0] == '0':
        idx = len(n)
        for digit in "123456789":
            if n.find(digit) != -1:
                idx = min(idx, n.find(digit))
        
        if idx == len(n):
            return idx
        
        n = swap(n, 0, idx)
        extra = idx
    
    return res + calc(n, last_digits) + extra


def brute(n):
    q = queue.Queue()
    dis = dict()
    
    q.put(str(n))
    dis[str(n)] = 0
    
    while not q.empty():
        s = q.get()
        if int(s) % 25 == 0:
            return dis[s]
        
        for i in range(1, len(s)):
            j = i - 1
            t = swap(s, i, j)
            
            if t not in dis and t[0] != '0':
                dis[t] = dis[s] + 1
                q.put(t)
    
    return -1


def swap(s, i, j):
    chars = list(s)
    chars[i], chars[j] = chars[j], chars[i]
    return "".join(char for char in chars)


def __starting_point():
    main()

__starting_point()

s = input()

if int(s)%25 == 0:
    print(0)
else:
    sols = []
    d = {}
    n = list(s)
    nr = s[::-1]
    for c in ('0', '2', '5', '7'):
        p = nr.find(c)
        d[c] = p
            
    for c1, c2 in (('2', '5'),('5', '0') , ('7', '5')):
        if c1 not in n or c2 not in n:
            continue
        
        dc1 = d[c1]
        dc2 = d[c2]
        sol = 0
        
        if dc1 == len(n) - 1 and len(n)>1 and n[1] == '0':
            i = 1
            while i<len(n) and (n[i] == '0' or dc2 == i ):
                i+=1
            if i!=len(n):
                i-=1
                sol = i
                dc1 -= 1
                if dc2 > len(n) -i -1:
                    dc2 -= 1
        
        if dc2 == len(n) - 1 and len(n)>1 and n[1] == '0':
            
            i = 1
            while i<len(n) and (n[i] == '0' or dc1 == i ):
                i+=1
            if i!=len(n):
                
                sol = i
                dc2 -= 1
                if dc1 > len(n) -i -1:
                    dc1 -= 1           
        
        
        if dc1 == 0:
            sols.append(dc2 + sol)
            continue
        
        if dc1 < dc2:
            sols.append(dc2 + dc1 + sol)
            
        else:
            sols.append(dc2 + dc1 - 1 + sol)

    z1 = nr.find('0')
    if z1!=-1:
        z2 = nr.find('0', z1+1)
        if z2 != -1:
            sols.append(z1 + z2 - 1)
    if len(sols) == 0:
        print(-1)
    else:
        print(min(sols))



y = input()
fives = (y.count('5'))
zeroes = (y.count('0'))
twos = (y.count('2'))
sevens = (y.count('7'))

if fives == 0:
    if zeroes < 2:
        print(-1)
        return
else:
    if zeroes == 0 and twos == 0 and sevens == 0:
        print(-1)
        return


best = 5 * len(y)
y = y[::-1]
for xx in [['5','2'], ['0','0'], ['5','7'], ['0','5'] ]:
    z = y
    count = 0
    for x in xx:        
        if not x in z:
            count = 5 * len(y)
            break
        f = z.index(x)
        z = z[:f] + z[f+1:]        
        
        count += f
    if len(z) > 2 and z[-1] == '0':
        valid = False 
        for x in z[::-1]:
            if x == '0':
                count += 1
                continue
            else:
                valid = True
                break
        if not valid:
            count += 5 * len(y)

    if count < best:
        best = count

print(best)

inf = float('inf')


def find_right(s, c, j=-1):
    for i in range(len(s)-1, -1, -1):
        if i != j and s[i] == c:
            return i
    return inf


def swaps(s, c1, c2):
    if len(s) > 1 and s[-2:] == c1 + c2:
        return 0

    if len(s) > 1 and s[-2:] == c2 + c1:
        return 1

    i2 = find_right(s, c2)
    if i2 == inf:
        return inf

    i1 = find_right(s, c1, i2)
    if i1 == inf:
        return inf

    ans = 0
    if i2 < i1:
        ans += abs(len(s) - 2 - (i1 - 1)) + abs(len(s) - 1 - i2)
    else:
        ans += abs(len(s) - 2 - i1) + abs(len(s) - 1 - i2)

    s0 = ''.join([si for i, si in enumerate(s) if i != i1 and i != i2])
    for i in range(len(s0)):
        if s0[i] != '0':
            ans += i
            break
    else:
        return inf

    return ans


n = input().strip()
ans = min(swaps(n, "0", "0"), swaps(n, "2", "5"), swaps(n, "5", "0"), swaps(n, "7", "5"))
print(ans if ans != inf else -1)


a = input()[::-1]
d = ['52','05','57']
if len(a)<2: print(-1)
else:
    if a[:2] in d:
        print(0)
    else:
        ans = 99999999
        if len([i for i in a if i =='0']) >=2:
            x,y=-1,-1
            for i in range(len(a)):
                if a[i] == '0':
                    if x<0:x = i
                    elif y<0:y = i
                    else:break
            ans = x+y-1
            
            
        for p in d:
            x,y = -1,-1
            for i in range(len(a)):
                if a[i] == p[0] and x<0:
                    x = i
                if a[i] == p[1] and y<0:
                    y = i
            if x<0 or y<0: continue
            # print(x,y)
            c = 0
            if x>y:
                c+=1
                x,y = y,x
            if y == len(a)-1 and a[-2] == '0' and x != len(a)-2:
                # print('-', c)
                z = -1
                for i in range(len(a)-1):
                    if a[i]!='0' and i != x:
                        z=i
                if z > 0:    
                    c+=len(a)-2-z
            c+=x+y-1
            # print(c)
            ans = min(ans,c)
        if ans == 99999999: ans = -1
        print(ans)

k = input()
import sys
Min = sys.maxsize
if '5' in k and '0' in k:
    temp = (len(k)-2) - k.rfind('5') + (len(k)-1) - k.rfind('0') 
    if (k.rfind('5') > k.rfind('0')):
        add = 0
        i = 1
        while k[i] == '0':
            add += 1
            i += 1
        temp += add
    if (temp<Min):
        Min = temp
if '2' in k and '5' in k:
    temp = (len(k)-2) - k.rfind('2') + (len(k)-1) - k.rfind('5') 
    if k.rfind('5')==0 and k[1]=='0' and len(k)>3:
        add = 0
        i = 1
        while k[i] == '0':
            add += 1
            i += 1
        temp += add
    if (k.rfind('2') > k.rfind('5')):
        temp += 1
    if (temp<Min):
        Min = temp
if '7' in k and '5' in k:
    temp = (len(k)-2) - k.rfind('7') + (len(k)-1) - k.rfind('5') 
    if k.rfind('5')==0 and k[1]=='0' and len(k)>3:
        add = 0
        i = 1
        while k[i] == '0':
            add += 1
            i += 1
        temp += add
    if (k.rfind('7') > k.rfind('5')):
        temp += 1
    if (temp<Min):
        Min = temp
if k.count('0')>1:
    css = k.rfind('0')
    temp = (len(k)-1) - css
    k = k[:css] + k[css+1:] 
    temp += (len(k)-1) - k.rfind('0') 
    if (temp<Min):
        Min = temp
if Min==sys.maxsize:
    print(-1)
else:
    print(Min)

k = input()
import sys
Min = sys.maxsize
if '5' in k and '0' in k:
    temp = (len(k)-2) - k.rfind('5') + (len(k)-1) - k.rfind('0') 
    if (k.rfind('5') > k.rfind('0')):
        temp += 1
    if (temp<Min):
        Min = temp
if '2' in k and '5' in k:
    temp = (len(k)-2) - k.rfind('2') + (len(k)-1) - k.rfind('5') 
    if k.rfind('5')==0 and k[1]=='0' and len(k)>3:
        add = 0
        i = 1
        while k[i] == '0':
            add += 1
            i += 1
        temp += add
    if (k.rfind('2') > k.rfind('5')):
        temp += 1
    if (temp<Min):
        Min = temp
if '7' in k and '5' in k:
    temp = (len(k)-2) - k.rfind('7') + (len(k)-1) - k.rfind('5') 
    if k.rfind('5')==0 and k[1]=='0' and len(k)>3:
        add = 0
        i = 1
        while k[i] == '0':
            add += 1
            i += 1
        temp += add
    if (k.rfind('7') > k.rfind('5')):
        temp += 1
    if (temp<Min):
        Min = temp
if k.count('0')>1:
    css = k.rfind('0')
    temp = (len(k)-1) - css
    k = k[:css] + k[css+1:] 
    temp += (len(k)-1) - k.rfind('0') 
    if (temp<Min):
        Min = temp
if Min==sys.maxsize:
    print(-1)
else:
    print(Min)

k = input()
n = len(k)
import sys
Min = sys.maxsize
ck = ['50','25','75']
for c in ck:
    if c[0] in k and c[1] in k:
        temp = 2*n - 3 - k.rfind(c[0]) - k.rfind(c[1]) 
        if (c[1]=='5'):
            if k.rfind('5')==0 and k[1]=='0' and n>3:
                add = 0
                i = 1
                while k[i] == '0':
                    add += 1
                    i += 1
                temp += add
        temp += k.rfind(c[0]) > k.rfind(c[1])
        Min = min(temp,Min)
if k.count('0')>1:
    css = k.rfind('0')
    temp = n-1 - css
    k = k[:css] + k[css+1:] 
    temp += len(k)-1 - k.rfind('0')
    Min = min(temp,Min)
print([Min,-1][Min==sys.maxsize])

s = input();n=len(s)
def i(c,o=0): 
    try: return s[::-1].index(str(c),o)
    except: return -1
oo=0
while oo<n-1 and s[oo+1]=='0':oo+=1
o5=i(5)
o7=i(7)
o2=i(2)
o01=i(0);o02=i(0,o01+1) if o01>=0 else -1
r=100
if o01>=0 and o02>=0: r=min(r,o01+o02-1)
if o01>=0 and o5>=0: r=min(r,o01+o5-int(o01<o5))
if o5>=0 and o2>=0: r=min(r,o5+o2-int(o5<o2)+int(o5==n-1 and oo))
if o5>=0 and o7>=0: r=min(r,o5+o7-int(o5<o7)+int(o5==n-1 and oo))
print(r if r<100 else -1)


l = [int(e) for e in input().strip()]

def lei00(l):
    result = []
    for i in range(len(l)-1, -1, -1):
        if l[i] == 0:
            result.append(i)
        if len(result) == 2:
            break
    if len(result) < 2:
        return None
    return 2 * len(l) - result[0] - result[1] - 3

def lei(l, x, y):
    assert x != y

    ix = None
    iy = None

    for i in range(len(l)-1, -1, -1):
        if l[i] == x and ix == None:
            ix = i
        elif l[i] == y and iy == None:
            iy = i

        if ix != None and iy != None:
            break

    if ix == None or iy == None:
        return None

    result = 2 * len(l) - ix - iy - 3

    if ix > iy:
        result += 1

    if x == 7 or x == 2:
        assert y == 5
        if iy == 0 and l[1] == 0:
            if len(l) >= 4:
                iii = 1
                while True:
                    iii += 1
                    if l[iii] != 0:
                        break
                result += iii-1
            if len(l) == 3:
                return None


    return result


l = [lei00(l), lei(l, 5, 0), lei(l, 7, 5), lei(l, 2, 5)]


result = None
for e in l:
    if e == None:
        continue
    if result == None or result > e:
        result = e

if result == None:
    print(-1)
else:
    print(result)







l = [int(e) for e in input().strip()]

def lei00(l):
    result = []
    for i in range(len(l)-1, -1, -1):
        if l[i] == 0:
            result.append(i)
        if len(result) == 2:
            break
    if len(result) < 2:
        return None
    return 2 * len(l) - result[0] - result[1] - 3

def lei(l, x, y):
    assert x != y

    ix = None
    iy = None

    for i in range(len(l)-1, -1, -1):
        if l[i] == x and ix == None:
            ix = i
        elif l[i] == y and iy == None:
            iy = i

        if ix != None and iy != None:
            break

    if ix == None or iy == None:
        return None

    result = 2 * len(l) - ix - iy - 3

    if ix > iy:
        result += 1

    if x == 7 or x == 2:
        assert y == 5
        if iy == 0 and l[1] == 0:
            if len(l) >= 4:
                iii = 1
                while True:
                    iii += 1
                    if l[iii] != 0:
                        break
                result += iii-1
            if len(l) == 3:
                return None


    return result


l = [lei00(l), lei(l, 5, 0), lei(l, 7, 5), lei(l, 2, 5)]


result = None
for e in l:
    if e == None:
        continue
    if result == None or result > e:
        result = e

if result == None:
    print(-1)
else:
    print(result)




n = input()
#if int(n) % 25 == 0:
#	print(0)
#	quit()

n = list(n)
if (not("5" in n)) and (not("0" in n)) and (not("7" in n)) and (not("2" in n)):
	print(-1)
	quit()
	
wkn = []
wkn[:] = n
ans = -1
for i in reversed(list(range(len(n)))):
	if (n[i] == "0"):
		wk1 = n[:i] + n[i + 1:] + [n[i]]
		ans = len(n) - i - 1
		if wk1[0] != "0":
			n[:] = wk1
			break
		else:
			count = 0
			f1 = True
			for j in wk1:
				count += 1
				if j != "0":
					f1 = False
					break
			if f1:
				ans = -1
				break
			ans += count - 1
			wk1 = [wk1[count - 1]] + wk1[:count - 1] + wk1[count:]
			n[:] = wk1
			break

if ans != -1:
	f = True
	for i in reversed(list(range(len(n) - 1))):
		if (n[i] == "0") or (n[i] == "5"):
			wk1 = n[:i] + n[i + 1:-1] + [n[i]]
			ans += len(n) - i - 2
			if wk1[0] != "0":
				f = False
				break
			else:
				count = 0
				f1 = True
				for j in wk1:
					count += 1
					if j != "0":
						f1 = False
						break
				if f1:
					ans = -1
					break
				ans += count - 1
				f = False
				break
	if f:
		ans = -1
			
wkans = ans

ans = -1
n = wkn
for i in reversed(list(range(len(n)))):
	if (n[i] == "5"):
		wk1 = n[:i] + n[i + 1:] + [n[i]]
		ans = len(n) - i - 1
		if wk1[0] != "0":
			n[:] = wk1
			break
		else:
			count = 0
			f1 = True
			for j in wk1:
				count += 1
				if j != "0":
					f1 = False
					break
			if f1:
				ans = -1
				break
			ans += count - 1
			wk1 = [wk1[count - 1]] + wk1[:count - 1] + wk1[count:]
			n[:] = wk1
			break
			
if ans != -1:
	f = True
	for i in reversed(list(range(len(n) - 1))):
		if (n[i] == "7") or (n[i] == "2"):
			wk1 = n[:i] + n[i + 1: -1] + [n[i]]
			ans += len(n) - i - 2
			if wk1[0] != "0":
				f = False
				break
			else:
				count = 0
				f1 = True
				for j in wk1:
					count += 1
					if j != "0":
						f1 = False
						break
				if f1:
					ans = -1
					break
				ans += count - 1
				f = False
				break
	if f:
		ans = -1
				
if (wkans == -1):
	print(ans)
	quit()
if (ans == -1):
	print(wkans)
	quit()
print(min(ans, wkans))


num = str(input())
n =len(num)
num_r = num[::-1]
s0, s5 = num_r.find('0'),num_r.find('5')
if s0 != -1:
    newnum_r = num_r[:s0] + num_r[s0+1:]
    c= []
    for a in ['0','5']:
        if newnum_r.find(a) != -1:
            c.append(newnum_r.find(a))
    if c != []:
        s = min(c)
        s0 = s0 + s
    else:
        s0 = 999999999
else:
    s0 = 999999999
if s5 != n-1 or num.find('0') != 1:
    if s5 != -1:
        newnum_r = num_r[:s5] + num_r[s5+1:]
        c= []
        for a in ['2','7']:
            if newnum_r.find(a) != -1:
                c.append(newnum_r.find(a))
        if c != []:
            s = min(c)
            s5 = s5 + s
        else:
            s5 = 999999999
    else:
        s5 = 999999999
    ssr = min(s0,s5)
    if ssr != 999999999:
        print(ssr)
    else:
        print(-1)
else:
    if s5 != -1:
        newnum_r = num_r[:s5] + num_r[s5+1:]
        c= []
        for a in ['2','7']:
            if newnum_r.find(a) != -1:
                c.append(newnum_r.find(a))
        if c != []:
            s = min(c)
            sk = 0
            for i in range(1,n-1):
                if num[i] == '0':
                    sk = sk + 1
                else:
                    break
            s5 = s5 + s + sk
        else:
            s5 = 999999999
    else:
        s5 = 999999999
    ssr = min(s0,s5)
    if ssr != 999999999:
        print(ssr)
    else:
        print(-1)

import sys
num = input()
length = len(num)
minimum = sys.maxsize
possibles = ["25", "50", "75", "00"]

for possible in possibles:
    if possible[0] == possible[1] and num.count('0') > 1:
        first = num.rfind(possible[0])
        second = num[:first].rfind(possible[1])
        temp_min = length - 2 - second + length - 1 - first
        minimum = min(minimum, temp_min)
    elif possible[0] != possible[1] and possible[0] in num and possible[1] in num:
        first = num.rfind(possible[0])
        second = num.rfind(possible[1])
            
        temp_min = length - 2 - first + length - 1 - second
        
        if (second == 0) and length > 3:
            i = 1
            while num[i] == '0':
                temp_min += 1
                i += 1
        
        if first > second:
            temp_min += 1
        minimum = min(minimum, temp_min)

if minimum == sys.maxsize:
    print(-1)
else:
    print(minimum)

s = input();n=len(s)
def i(c,o=0): 
    try: return s[::-1].index(str(c),o)
    except: return -1
oo=0
while oo<n-1 and s[oo+1]=='0':oo+=1
o5=i(5)
o7=i(7)
o2=i(2)
o01=i(0);o02=i(0,o01+1) if o01>=0 else -1
r=100
if o01>=0 and o02>=0: r=min(r,o01+o02-1)
if o01>=0 and o5>=0: r=min(r,o01+o5-int(o01<o5))
if o5>=0 and o2>=0: r=min(r,o5+o2-int(o5<o2)+int(o5==n-1 and oo))
if o5>=0 and o7>=0: r=min(r,o5+o7-int(o5<o7)+int(o5==n-1 and oo))
print(r if r<100 else -1)

s=input()[::-1]
m=I=41
f=s.find('5')+1
i=s.find('0')+1
t=len(s)
if i:
 j=min(s.find('0',i)+1or I,f or I)
 if j<I:
  m=i+j-3
  if j<i:m+=1
if f:
 j=min(s.find('2')+1or I,s.find('7')+1or I)
 if j<I:
  l=f+j-3
  if j<f:l+=1
  if f==t:
   i=t-1
   while i==j or s[i-1]=='0':
    if i!=j:l+=1
    i-=1
   if i==j:l=I
  m=min(m,l)
print((-1,m)[m<I])


s=input()[::-1]
m=I=41
f=s.find('5')+1
i=s.find('0')+1
t=len(s)
if i:
 j=min(s.find('0',i)+1or I,f or I)
 if j<I:
  m=i+j-3
  if j<i:m+=1
if f:
 j=min(s.find('2')+1or I,s.find('7')+1or I)
 if j<I:
  l=f+j-3
  if j<f:l+=1
  if f==t:
   i=t-1
   while i==j or s[i-1]=='0':
    if i!=j:l+=1
    i-=1
  m=min(m,l)
print((-1,m)[m<I])

s=input()[::-1]
m=I=41
f=s.find('5')+1
i=s.find('0')+1
t=len(s)
if i:
 j=min(s.find('0',i)+1or I,f or I)
 if j<I:
  m=i+j-3
  if j<i:m+=1
if f:
 j=min(s.find('2')+1or I,s.find('7')+1or I)
 if j<I:
  l=f+j-3
  if j<f:l+=1
  if f==t:
   i=t-1
   while s[i-1]=='0':
    if i!=j:l+=1
    i-=1
  m=min(m,l)
print((-1,m)[m<I])


s=input()[::-1]
m=I=41
f=s.find('5')+1
i=s.find('0')+1
t=len(s)
if i:
 j=min(s.find('0',i)+1or I,f or I)
 if j<I:
  m=i+j-3
  if j<i:m+=1
if f:
 j=min(s.find('2')+1or I,s.find('7')+1or I)
 if j<I:
  l=f+j-3
  if j<f:l+=1
  if f==t:
   i=t-1
   while s[i-1]=='0':
    l+=1;i-=1
  m=min(m,l)
print((-1,m)[m<I])

s=input()[::-1]
t=len(s)
m=I=40
def g(c,i=0):return s.find(str(c),i)+1 or I
i,f=g(0),g(5)
if i<I:
 j=min(g(0,i),f)
 if j<I:
  m=i+j-3
  if j<i:m+=1
if f<I:
 j=min(g(2),g(7))
 if j<I:
  l=f+j-3
  if j<f:l+=1
  if f==t:
   i=t-1
   while s[i-1]=='0':
    l+=1;i-=1
  m=min(m,l)
print((-1,m)[m<I])

s=input()[::-1]
t=len(s)
m=I=40
def g(c,i=0):return s.find(str(c),i)+1 or I
i,f=g(0),g(5)
if i<I:
 j=min(g(0,i),f)
 if j<I:m=i+j-3+(j<i)
if f<I:
 j=min(g(2),g(7))
 if j<I:
  l=f+j-3
  if j<f:l+=1
  if f==t:
   i=t-1
   while s[i-1]=='0':
    l+=1;i-=1
  m=min(m,l)
print((-1,m)[m<I])

s=input()[::-1]
t=len(s)
m=I=40
def g(c,i=0):return s.find(str(c),i)+1 or I
i,f=g(0),g(5)
if i<I:
 j=min(g(0,i),f)
 if j<I:m=i+j-3+(j<i)
if f<I:
 j=min(g(2),g(7))
 if j<I:
  l=f+j-3+(j<f)
  if f==t:
   i=t-1
   while s[i-1]=='0':
    l+=1;i-=1
  m=min(m,l)
print((-1,m)[m<I])

s=input()[::-1]
t=len(s)
I=50
def g(c,i=0):return s.find(str(c),i)+1 or I
i,f=g(0),g(5)
j=min(g(0,i),f)
m=i+j-3+(j<i)
if f<I:
 j=min(g(2),g(7))
 if j<I:
  l=f+j-3+(j<f)
  if f==t:
   i=t-1
   while s[i-1]=='0':
    l+=1;i-=1
  m=min(m,l)
print((-1,m)[m<40])

s=input()[::-1]
t=len(s)
def g(c,i=0):return s.find(str(c),i)+1or 50
i,f=g(0),g(5)
j=min(g(0,i),f)
m=i+j-3+(j<i)
j=min(g(2),g(7))
l=f+j-3+(j<f)
if f==t:
 i=t-1
 while s[i-1]=='0':
  l+=1;i-=1
m=min(m,l)
print((-1,m)[m<40])