Luba has a ticket consisting of 6 digits. In one move she can choose digit in any position and replace it with arbitrary digit. She wants to know the minimum number of digits she needs to replace in order to make the ticket lucky.

The ticket is considered lucky if the sum of first three digits equals to the sum of last three digits.


-----Input-----

You are given a string consisting of 6 characters (all characters are digits from 0 to 9) — this string denotes Luba's ticket. The ticket can start with the digit 0.


-----Output-----

Print one number — the minimum possible number of digits Luba needs to replace to make the ticket lucky.


-----Examples-----
Input
000000

Output
0

Input
123456

Output
2

Input
111000

Output
1



-----Note-----

In the first example the ticket is already lucky, so the answer is 0.

In the second example Luba can replace 4 and 5 with zeroes, and the ticket will become lucky. It's easy to see that at least two replacements are required.

In the third example Luba can replace any zero with 3. It's easy to see that at least one replacement is required.

Difficulty: interview

Starter code:

Solutions:
x=int(input())
def s(a):
  r=0
  while a>0:
    r+=a%10
    a//=10
  return r
def d(a,b):
  r=0
  for i in range(6):
    if a%10!=b%10:
      r += 1
    a//=10
    b//=10
  return r
c=6
for i in range(1000000):
  if s(i%1000)==s(i//1000):
    c=min(c,d(x,i))
print(c)


s = input()

ans = 6

for i in range (0, 10):
    for j in range (0, 10):
        for k in range(0, 10):
            for f in range (0, 10):
                for f1 in range(0, 10):
                    for f2 in range(0, 10):
                        if(i + j + k == f + f1 + f2):
                            cnt = 0
                            if i != (ord(s[0]) - ord('0')):
                                cnt = cnt + 1
                            if j != (ord(s[1]) - ord('0')):
                                cnt = cnt + 1
                            if k != (ord(s[2]) - ord('0')):
                                cnt = cnt + 1
                            if f != (ord(s[3]) - ord('0')):
                                cnt = cnt + 1
                            if f1 != (ord(s[4]) - ord('0')):
                                cnt = cnt + 1
                            if f2 != (ord(s[5]) - ord('0')):
                                cnt = cnt + 1
                        ans = min(ans, cnt)
print(ans)

def f(x):
	return sum(x[:3]) == sum(x[3:])

def main():
	a = [int(i) for i in input()]
	if f(a):
		return 0
	for i in range(6):
		for j in range(10):
			b = a[:]
			b[i] = j
			if f(b):
				return 1
	for i in range(6):
		for j in range(i):
			for k in range(10):
				for l in range(10):
					b = a[:]
					b[i] = k
					b[j] = l
					if f(b):
						return 2
	return 3

print(main())



s = input()
l = []
for d in s[:3]:
  l.append(int(d))
u = []
for d in s[3:]:
  u.append(int(d))
  
if sum(l) == sum(u):
  print(0)
else:
  if sum(l) > sum(u):
    l, u = u, l
  
  diffs = sorted(list([9-x for x in l]) + u)[::-1]
  #print(diffs)
  for i in range(1,7):
    if sum(diffs[:i]) >= sum(u) - sum(l):
      print(i)
      break
  


s = input()

l1 = [int(s[i]) for i in range(3)]
l2 = [int(s[3 + i]) for i in range(3)]

s1 = sum(l1)
s2 = sum(l2)

if (s1 < s2):
	l1, l2 = l2, l1
	s1, s2 = s2, s1

l1.sort(reverse = True)
l2.sort()

ans = 0

p1 = 0
p2 = 0

while s1 > s2:
	if l1[p1] > 9 - l2[p2]:
		s1 -= l1[p1]
		p1 += 1
	else:
		s2 += 9 - l2[p2]
		p2 += 1
	ans += 1 

print(ans)

from functools import reduce
e = input()

mi = 6

for i in range(1000000):
    a = str(i).zfill(6)

    s = ord((a)[0])+ ord((a)[1]) + ord((a)[2])
    t = ord((a)[3])+ ord((a)[4]) + ord((a)[5])

    if s == t:
        l = sum(list([0 if x[0] == x[1] else 1 for x in zip(a, e)]))
        mi = min(mi, l)

print(mi)


s=input()
a=[0,0,0,0,0,0]
t=[]
ans=3
for i in s:
    t.append(ord(i)-ord('0'))

for a[0] in range(10):
    for a[1] in range(10):
        for a[2] in range(10):
            for a[3] in range(10):
                for a[4] in range(10):
                    for a[5] in range(10):
                        anss=6
                        if a[0]+a[1]+a[2] == a[3]+a[4]+a[5]:
                            for i in range(6):
                                if a[i]==t[i]:
                                    anss=anss-1
                        if anss<ans:
                            ans=anss
print(ans)


s = input()
a = list(map(int, s[:3]))
b = list(map(int, s[3:]))
al = sum(a)
bl = sum(b)
dif = al - bl
cnt = 0
while dif < 0:
    cnt += 1
    if 9 - min(a) > max(b):
        dif += min(-dif, 9 - min(a))
        a[a.index(min(a))] = 9
    else:
        dif += min(-dif, max(b))
        b[b.index(max(b))] = 0

c = b[:]
b = a[:]
a = c[:]
while dif > 0:
    cnt += 1
    if 9 - min(a) > max(b):
        dif -= min(dif, 9 - min(a))
        a[a.index(min(a))] = 9
    else:
        dif -= min(dif, max(b))
        b[b.index(max(b))] = 0

print(cnt)

def comp(n, m):
    rtn = 0
    for i in range(6):
        if n[i] != m[i]:
            rtn += 1
    return rtn


n = list(map(int, list(input())))
ans = 6
for i in range(1000000):
    m = []
    for _ in range(6):
        m.append(i % 10)
        i //= 10
    m = list(reversed(m))
    if sum(m[:3]) == sum(m[3:]):
        ans = min(ans, comp(n, m))

print(ans)



import sys

def debug(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)

a = [int(ch) for ch in input()]
assert(len(a) == 6)
b1 = a[0:3]
b2 = a[3:6]
if sum(b1) > sum(b2):
    b1, b2 = b2, b1
diff = sum(b2) - sum(b1)
# debug("diff =", diff)

deltas = sorted([9-x for x in b1 if x < 9] + [x for x in b2 if x > 0], reverse=True)
# debug("deltas =", deltas)
cum_deltas = [0] + deltas[:]

for i in range(1, len(cum_deltas)):
    cum_deltas[i] += cum_deltas[i-1]
for i, x in enumerate(cum_deltas):
    if cum_deltas[i] >= diff:
        break

# debug("cum_deltas =", cum_deltas)
print(i)


digits = [int(x) for x in input()]


difference = sum(digits[0:3]) - sum(digits[3:])

helper = []
if difference < 0:
    helper = [9 - x for x in digits[:3]] + digits[3:]
else:
    helper = digits[:3] + [9 - x for x in digits[3:]]

helper = sorted(helper)[::-1]
n = 0

sum_ = 0
for x in helper:
    if sum_ >= abs(difference):
        break

    sum_ += x
    n += 1

print(n)


# IAWT
S = input()
a = S[:3]
b = S[3:]

def Sum(st):
    n = 0
    for x in st:
        n += int(x)
    return n

def g(s, t): # s < t
    diff = int(t[0])+int(t[1])+int(t[2])-int(s[0])-int(s[1])-int(s[2])
    ma = 9 - int(s[0])
    c = 0
    if 9 - int(s[1]) > ma:
        c = 1
        ma = 9 - int(s[c])
    if 9 - int(s[2]) > ma:
        c = 2
        ma = 9 - int(s[c])
    
    mm = int(t[0])
    c2 = 0
    if int(t[1]) > mm:
        mm = int(t[1])
        c2 = 1
    if int(t[2]) > mm:
        mm = int(t[2])
        
        c2 = 2
    if ma > mm:
        C = str(int(s[c]) + min(diff, ma))
        s = s[:c] + C + s[c+1:]
    else:
        C = str(int(t[c2]) - min(diff, mm))
        t = t[:c2] + C + t[c2+1:]
    return s, t


def f():
    nonlocal a, b
    if Sum(a) == Sum(b):
        print(0)
        return
    if Sum(a) < Sum(b):
        n = 0
        while (Sum(a) != Sum(b)):
            a, b = g(a, b)
            n += 1
        print(n)
        return
    n = 0
    while (Sum(a) != Sum(b)):
        b, a = g(b, a)
        n += 1
    print(n)

f()


ticket = input()
q1, q2 = [(int(i), j) for j, i in enumerate(ticket[:3])], [(int(i), j) for j, i in enumerate(ticket[3:])]
p1, p2 = [i for i, j in q1], [i for i, j in q2]

if sum(p1) > sum(p2):
	p1, p2 = p2, p1
	q1, q2 = q2, q1

if sum(p1) == sum(p2):
	print(0)
	return

for i in range(20):
	if 9 - min(p1) > max(p2):
		pos = min(q1)[1]
		p1[pos] = 9
		q1[pos] = (9, pos)
	else:
		pos = max(q2)[1]
		p2[pos] = 0
		q2[pos] = (0, pos)
	if sum(p1) >= sum(p2):
		print(i + 1)
		return



digit_set = set(range(10))
double_digit_set = set(range(19))
A = [int(i) for i in input()]
first_sum = sum(A[:3])
second_sum = sum(A[3:])
one_flag = True
exit_flag = False
if first_sum == second_sum:
    print(0)
else:
    for i in range(6):
        if i < 3:
            if second_sum - (first_sum - A[i]) in digit_set:
                print(1)
                one_flag = False
                break
        else:
            if first_sum - (second_sum - A[i]) in digit_set:
                print(1)
                one_flag = False
                break
    if one_flag:
        for i in range(6):
            for j in range(i+1, 6):
                if i < 3 and j < 3:
                    if second_sum - (first_sum - A[i] - A[j]) in double_digit_set:
                        print(2)
                        exit_flag = True
                        break
                if i >= 3 and j >= 3:
                    if first_sum - (second_sum - A[i] - A[j]) in double_digit_set:
                        print(2)
                        exit_flag = True
                        break
                elif abs(first_sum - A[i] - second_sum + A[j]) <= 9:
                    print(2)
                    exit_flag = True
                    break
            if exit_flag:
                break
        else:
            print(3)







i = list([int(c) for c in input()])

d = sum([i[3]-i[0], i[4]-i[1], i[5]-i[2]])

if(d < 0):
    i.reverse()
    d *= -1

for z in range(3):
    i[z] = 9 - i[z]

i = sorted(i)
i.reverse()

ir = 0
for (ind, z) in enumerate(i):
    if ir >= d:
        print(ind)
        break
    ir += z




def lucky(s):
    ds = []

    while s:
        ds.append(s % 10)
        s //= 10

    while len(ds) < 6:
        ds.append(0)


    return ds[0] + ds[1] + ds[2] == ds[3] + ds[4] + ds[5]


def difs(a, b):
    d = 0

    while a or b:
        if a % 10 != b % 10:
            d += 1

        a //= 10
        b //= 10

    return d


def main():
    s = int(input())

    min_difs = 10
    end = 10 ** 6

    for s_t in range(0, end):
        if lucky(s_t):
#            import pdb; pdb.set_trace()
            min_difs = min(min_difs, difs(s, s_t))
            
            if min_difs == 0:
                break

    print(min_difs)


def __starting_point():
    main()





__starting_point()

def change_num(left_arr, right_arr, count):
    min_n, max_n = 10, -1
        
    if sum(left_arr) > sum(right_arr):
        max_arr = left_arr
        min_arr = right_arr
    else:
        max_arr = right_arr
        min_arr = left_arr
        
    diff = sum(max_arr) - sum(min_arr)
    
    for i in range (3):
        if min_n > min_arr[i]:
            min_n = min_arr[i]
            min_i = i
        if max_n < max_arr[i]:
            max_n = max_arr[i]
            max_i = i
    if diff <= 9-min_n:
        count += 1
        return count
    elif diff <= max_n:
        count += 1
        return count
    elif max_n >= 9-min_n:
        max_arr[max_i] = 0
    else:
        min_arr[min_i] = 9
    count += 1
    return change_num(min_arr, max_arr, count)

msg = input() 

left = msg[:3]
right = msg[3:]

left_arr = []
right_arr = []

for char in left:
    left_arr.append(int(char))
for char in right:
    right_arr.append(int(char))

if sum(left_arr) == sum(right_arr):
    print(0)
else:
    print(change_num(left_arr, right_arr, 0))



s = input()
arr = [int(i) for i in s]
count = 0
while count < 4:
    a = arr[0] + arr[1] + arr[2]
    b = arr[3] + arr[4] + arr[5]
    r = abs(a - b)
    if a == b:
        print(count)
        return
    if a < b:
        num_min = arr.index(min(arr[0], arr[1], arr[2]))
        num_max = arr.index(max(arr[3], arr[4], arr[5]))
    else:
        num_min = arr.index(min(arr[3], arr[4], arr[5]))
        num_max = arr.index(max(arr[0], arr[1], arr[2]))

    if r <= arr[num_max]:
        print(count + 1)
        return
    if r <= 9 - arr[num_min]:
        print(count + 1)
        return
    if 9 - arr[num_min] > arr[num_max]:
        arr[num_min] = 9
    else:
        arr[num_max] = 0
    count += 1
print(count)


digs = list(map(int, input()))

l, r = min(digs[:3], digs[3:], key=sum), max(digs[:3], digs[3:], key=sum)

ans = 0
while sum(r) - sum(l) > 0:
    if 9 - min(l) >= max(r):
        diff = 9 - min(l)
        l[l.index(min(l))] = 9
    else:
        diff = max(r)
        r[r.index(max(r))] = 0
    ans += 1

print(ans)


def work():
    s = input()
    a = [int(s[0]), int(s[1]), int(s[2])]
    b = [int(s[3]), int(s[4]), int(s[5])]
    if sum(a) == sum(b):
        print(0)
        return
    if sum(a) > sum(b):
        a, b = b, a
    # now sum(a) < sum(b)
    a = sorted(a)
    b = sorted(b)
    ben = [9-a[0], 9-a[1], 9-a[2], b[0], b[1], b[2]]
    ben = sorted(ben)[::-1]
    k = sum(b) - sum(a)
    t = 0
    i = 0
    while t < k:
        t += ben[i]
        i += 1
    print(i)
    return
        

work()


n = input()
a, b, c, d, e, f = list(map(int, n))

def g(a, b, c, s):
    m1, m2, m3 = sorted([a, b, c])
    if s == a + b+ c:
        return 0
    elif s > a+ b+c:
        s1 = a + b + c
        if m2 + m3 + 9 >= s:
            return 1
        if m3 + 18 >= s:
            return 2
        else:
            return 3
    else:
        if m1 + m2 <= s:
            return 1
        if m1 <= s:
            return 2
        return 3

ll = []
for s in range(28):
    ll.append(g(a, b, c, s) + g(d, e, f, s))

print(min(ll))




n = input()
a, b, c, d, e, f = list(map(int, n))

def g(a, b, c, s):
    m1, m2, m3 = sorted([a, b, c])
    if s == a + b+ c:
        return 0
    elif s > a+ b+c:
        s1 = a + b + c
        if m2 + m3 + 9 >= s:
            return 1
        if m3 + 18 >= s:
            return 2
        else:
            return 3
    else:
        if m1 + m2 <= s:
            return 1
        if m1 <= s:
            return 2
        return 3

ll = []
for s in range(28):
    ll.append(g(a, b, c, s) + g(d, e, f, s))

print(min(ll))


'''a = int(input())
wow = input()

for i in wow:
    i = int(i)'''

wow = [int(e) for e in input()]

a1 = [wow[0],wow[1],wow[2]]
a2 = [wow[3],wow[4],wow[5]]

sum1 = sum(a1)
sum2 = sum(a2)

if(sum1 == sum2):
    print(0)
else:
    if(sum1 < sum2):
        noi = sum1
        mak = sum2
        fnoi = list(a1)
        fmak = list(a2)
        pontang = sum2-sum1
    if(sum2 < sum1):
        noi = sum2
        mak = sum1
        fnoi = list(a2)
        fmak = list(a1)
        pontang = sum1-sum2

    fnoi.sort()
    fmak.sort()

    ptfnoi = [0]*3
    ptfmak = [0]*3

    '''for i in range(3):
        ptfnoi.append(9-fnoi[i])
        ptfmak.append(fmak[i]-0)'''

    ptfnoi[0] = 9 - fnoi[0]
    ptfnoi[1] = 9 - fnoi[1]
    ptfnoi[2] = 9 - fnoi[2]
    ptfmak[0] = fmak[0]
    ptfmak[1] = fmak[1]
    ptfmak[2] = fmak[2]

    '''print(ptfnoi)
    print(ptfmak)'''

    lis = [ptfnoi[0],ptfnoi[1],ptfnoi[2],ptfmak[0],ptfmak[1],ptfmak[2]]
    lis.sort()
    mx1 = lis[5]
    mx2 = lis[4]

    if(mx1>=pontang):
        print(1)
    elif(mx1+mx2>=pontang):
        print(2)
    else:
        print(3)
        




a=[int(i) for i in input()]
if sum(a[3:])>sum(a[:3]):
    a[:3],a[3:]=a[3:],a[:3]
a[:3]=sorted(a[:3],reverse=True)
a[3:]=sorted(a[3:],reverse=True)
#print(a)

ans=0
i=0; j=5

while sum(a[:3])>sum(a[3:]):
    ans+=1
    #print(sum(a[:3]),sum(a[3:]),'i',i,'j',j)
    #print(a,'\n')
    if a[i]>9-a[j]:
        a[i]=0
        i+=1
    else:
        a[j]=9
        j-=1

#print(a,'\n')
print(ans)


l=list(input())
a=[]
b=[]
for i in range(3):
    a.append(int(l[i]))
for i in range(3,6):
    b.append(int(l[i]))
a.sort()
b.sort()
s1=sum(a)
s2=sum(b)

if(s1==s2):
    print(0)
else:
    if(s1<s2):
        diff=s2-s1
        a.sort()
        b.sort(reverse=True)
        c=[]
        t=0
        for i in range(3):
            c.append(9-a[i])
            c.append(b[i])
        c.sort(reverse=True)
        for i in range(6):
            t=t+c[i]
            if(t>=diff):
                break
        print(i+1)
    else:
        
        diff=s1-s2
        t=0
        a.sort(reverse=True)
        b.sort()
        c=[]
        for i in range(3):
            c.append(a[i])
            c.append(9-b[i])
        c.sort(reverse=True)
        for i in range(6):
            
            t=t+c[i]
            if(t>=diff):
                break
        print(i+1)