CodeEff/ECCO huggingface dataset:
# Original solution
import sys
from math import sqrt
from collections import Counter

input = sys.stdin.readline


def I():
    return int(sys.stdin.readline())


def MI():
    return list(map(int, sys.stdin.readline().split()))


inf = float("inf")
mod = 10 ** 9 + 7


def main():
    n, k = MI()
    a_list = MI()

    c = Counter(a_list)
    n_key = len(c)
    n_rewrite = 0
    while n_key > k:
        n_rewrite += c.pop(c.most_common()[-1][0])
        n_key -= 1

    print(n_rewrite)
    pass


if __name__ == "__main__":
    main()


# Optimized solution
import sys
from math import sqrt
from collections import Counter

input = sys.stdin.readline


def I():
    return int(sys.stdin.readline())


def MI():
    return list(map(int, sys.stdin.readline().split()))


inf = float("inf")
mod = 10 ** 9 + 7


def main():
    n, k = MI()
    a_list = MI()

    c = Counter(a_list)
    sum = 0
    if len(c) <= k:
        print("0")
        exit()

    for l in c.most_common()[k:]:
        sum += l[1]
    print(sum)
    pass


if __name__ == "__main__":
    main()
# Original solution
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
D = {}
for i in range(N) :
    if A[i] not in D :
        D[A[i]] = 1
    else :
        D[A[i]] += 1
L = list(D.values())
L = sorted(L)
ans = 0
for i in range(len(L)) :
    if len(L) > K :
        ans += L[0]
        L.pop(0)
print(ans)


# Optimized solution
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
D = {}
for i in A :
    if i in D :
        D[i] += 1
    else :
        D[i] = 1
D = sorted(list(D.items()),key=lambda x:x[1])
counter = 0
answer = 0
for j in range(len(D)) :
    if len(D) - counter > K :
        counter += 1
        answer += D[j][1]
    else :
        print(answer)
        break
# Original solution
N, K = [int(nk) for nk in input().split()]
A = [int(a) for a in input().split()]

A_set = list(set(A))
if len(A_set) <= K:
  print((0))
else:
  AA = [A.count(i) for i in A_set]
  AA.sort()
  ans = sum(AA[:-K])
  print(ans)

# Optimized solution
N, K = [int(nk) for nk in input().split()]
A = [int(a) for a in input().split()]

A_set = list(set(A))
if len(A_set) <= K:
  print((0))
else: # len(A_set) > K:
  dictionary = {}
  for n in A_set:
    dictionary[n] = 0
  for m in A:
    dictionary[m] += 1
  
  dict_val = list(dictionary.values())
  dict_val.sort(reverse = True)
  ans = N - sum(dict_val[:K])
  print(ans)
# Original solution
def 解():
    iN,iK = [int(_) for _ in input().split()]
    aA = [int(_) for _ in input().split()]
    dA = {}
    def addD(d,a):
        if a in d:
            d[a] += 1
        else:
            d[a] = 1
    for a in aA:
        addD(dA,a)
    aList = sorted(list(dA.items()),key=lambda x:x[1])
    print((sum([x[1] for x in aList[0:len(aList)-iK]])))
解()


# Optimized solution
def 解():
    iN,iK = [int(_) for _ in input().split()]
    #aA = [int(_) for _ in input().split()]
    dA = {}
    def addD(d,a):
        if a in d:
            d[a] += 1
        else:
            d[a] = 1
    for a in [int(_) for _ in input().split()]:
        addD(dA,a)
    aList = sorted(list(dA.items()),key=lambda x:x[1])
    print((sum([x[1] for x in aList[0:len(aList)-iK]])))
解()
# Original solution

N,K = list(map(int,input().split()))
balls = []
bucket = [0]*(N+1)

balls = list(map(int,input().split()))
balls.sort()

for ball_number in balls:
    bucket[ball_number] += 1

def judge(number_of_types, types):
    if number_of_types <= types:
        return True

number_of_types = 0
for i in bucket:
    if i >= 1:
        number_of_types += 1

if number_of_types <= K:
    print("0")
    quit()
else:
    count = 0
    for i in range(1,N+1):
        for j in bucket:
            if j == i:
                count += i
                number_of_types -= 1
                if judge(number_of_types, K):
                    print(count)
                    quit()

# Optimized solution
N,K=list(map(int,input().split()))
A=list(map(int,input().split()))
A.sort()
bucket=[0*i for i in range(N+1)]
count=1
types=1
for i in range(1,N):
    if A[i]==A[i-1]:
        if i!=N-1:
            count+=1
        else:
            count+=1
            bucket[count]+=1
            break
    else:
        types+=1
        if i!=N-1:
            bucket[count]+=1
            count=1
        else:
            bucket[count]+=1
            bucket[1]+=1
            break

i=1
number_of_changes=0
while True:
    if types<=K:
        print((0))
        quit()
    elif types-bucket[i]<=K:
        print(((types-K)*i+number_of_changes))
        quit()
    else:
        types-=bucket[i]
        number_of_changes+=bucket[i]*i
    i+=1
# Original solution
N, K = list(map(int,input().split()))
A = list(map(int,input().split()))

d = {}
for a in A:
  if(a not in d):
    d[a] = 1
  else:
    d[a] += 1

print((sum(sorted(d.values())[:-K])))

# Optimized solution
N, K = list(map(int,input().split()))
A = list(map(int,input().split()))
d = {}
for a in A:
  if(a in d):
    d[a] += 1
  else:
    d[a] = 1

print((sum(sorted(d.values())[:-K])))
# Original solution
n, k = list(map(int,input().split()))
a = list(map(int,input().split()))
d = []
c = []
for i in range(n):
    if not a[i] in d:
        d.append(a[i])
        c.append(a.count(a[i]))
c.sort(reverse=True)
print((n-sum(c[0:k])))


# Optimized solution
n, k = list(map(int,input().split()))
a = list(map(int,input().split()))
d = {}
for i in a:
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
c = sorted(list(d.items()),key = lambda x:x[1], reverse=True)
ans = 0
for i in range(min(k,len(c))):
    ans += c[i][1]

print((n-ans))
# Original solution
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))

from collections import Counter, OrderedDict

c = Counter(a)
d = OrderedDict(sorted(list(c.items()), key=lambda x: x[1]))

if len(d) <= k:
    print((0))

else:
    ans = 0
    while len(d) > k:
        item = list(d.items())[0]
        ans += item[1]
        del d[item[0]]
    print(ans)


# Optimized solution
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))

from collections import Counter

c = Counter(a)
d = c.most_common()

if len(d) <= k:
    print((0))

else:
    ans = 0
    while len(d) > k:
        item = d.pop()
        ans += item[1]
    print(ans)
# Original solution
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
cnt_list = []
cnt_dict = {}
for i in a:
    if i in cnt_dict:
        cnt_dict[i] += 1
    else:
        cnt_dict[i] = 1
cnt_dict_sorted = sorted(list(cnt_dict.items()), key=lambda x: x[1])
for i in set(a):
    cnt_list.append(a.count(i))
ans = 0
if len(cnt_dict_sorted) <= k:
    ans = 0
else:
    tmp = len(cnt_dict_sorted) - k
    for j in range(tmp):
        ans += cnt_dict_sorted[j][1]
print(ans)


# Optimized solution
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
cnt_dict = {}
for i in a:
    if i in cnt_dict:
        cnt_dict[i] += 1
    else:
        cnt_dict[i] = 1
cnt_dict_sorted = sorted(list(cnt_dict.items()), key=lambda x: x[1])
ans = 0
if len(cnt_dict_sorted) <= k:
    ans = 0
else:
    tmp = len(cnt_dict_sorted) - k
    for j in range(tmp):
        ans += cnt_dict_sorted[j][1]
print(ans)
# Original solution
n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
if len(list(set(a)))<=k:
  print((0))
else:
  l=[0]*n
  for i in range(n):
    l[a[i]-1]+=1
  l.sort()
  ans=0
  cnt=0
  i=0
  while cnt<(len(list(set(a)))-k):
    if l[i]!=0:
      ans+=l[i]
      cnt+=1
      i+=1
    else:
      i+=1
  print(ans)

# Optimized solution
n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
if len(list(set(a)))<=k:
  print((0))
else:
  d={}
  for i in range(n):
    if a[i] in d:
      d[a[i]]+=1
    else:
      d[a[i]]=1
  d=sorted(list(d.items()),key=lambda x:x[1])
  m=len(d)
  cnt=0
  for i in range((len(list(set(a))))-k):
    cnt+=d[i][1]
  print(cnt)
# Original solution
from collections import Counter
n,k=list(map(int,input().split()))
A=list(map(int,input().split()))
s=len(set(A))
C=Counter(A)
if s>k:
    for i in range(k):
        n-=C.most_common()[i][1]
    print(n)
else:
    print((0))

# Optimized solution
n,k=list(map(int,input().split()))
A=list(map(int,input().split()))
d={}
for a in A:
    if a in d:
        d[a]+=1
    else:
        d[a]=1
D=sorted(list(d.items()), key=lambda x:x[1], reverse=True)
if len(set(A))>k:
    for i in range(k):
        n-=D[i][1]
    print(n)
else:
    print((0))
# Original solution
#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
def main():
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))
    L = []
    B = set(A)
    for i in B:
        L.append(A.count(i))
    L.sort()
    if len(B) <= K:
        print('0')
    else:
        print((str(sum(L[0:len(B)-K]))))


if __name__ == "__main__":
    main()



# Optimized solution
#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
def main():
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))
    B = set(A)
    L = [0 for i in range(N+1)]
    for i in A:
        L[i] += 1
    L.sort()
    if len(B) <= K:
        print('0')
    else:
        print((str(sum(L[0:N+1-K]))))


if __name__ == "__main__":
    main()
# Original solution
from collections import Counter
n,k=list(map(int,input().split()))
a=Counter(list(map(int,input().split())))
cnt=0
ls=[]
if len(a)>k:
	for i in range(len(a)):
		ls.append(a.most_common()[i][1])
print((sum(ls[k:])))

# Optimized solution
n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
d={}
for i in a:
	d[i]=d.get(i,0)+1
s=sorted(d.values())
print((sum(s[:len(s)-k])))
# x
# Original solution
from collections import Counter
N,K = list(map(int, input().split()))
A = Counter(list(map(int, input().split())))
B = list(A.items())
k = len(B) - K
if k <= 0:
    print((0))
else:
    print((sum([sorted(B,key=lambda x:x[1])[i][1] for i in range(k)])))

# Optimized solution
from collections import Counter
N,K = list(map(int, input().split()))
A = Counter(list(map(int, input().split())))
B = list(A.values())
k = len(B) - K
if k <= 0:
    print((0))
else:
    print((sum(sorted(B)[0:k])))
# Original solution
from collections import Counter
N,K = list(map(int, input().split()))
A = Counter(list(map(int, input().split())))
B = list(A.values())
k = len(B) - K
if k <= 0:
    print((0))
else:
    print((sum(sorted(B)[0:k])))

# Optimized solution
from collections import Counter
N,K = list(map(int, input().split()))
A = Counter(input().split())
B = list(A.values())
k = len(B) - K
if k <= 0:
    print((0))
else:
    print((sum(sorted(B)[0:k])))
# Original solution
N,K = list(map(int,input().split(" ")))
A = list(map(int,input().split(" ")))
num = list(set(A))
ans=[]
for n in num:
    ans.append(A.count(n))
print((sum(sorted(ans)[:len(ans)-K:])))


# Optimized solution
N,K = list(map(int,input().split(" ")))
d={}
for i in input().split(" "):
    if i in d:
        d[i]+=1
    else:
        d[i]=1
print((sum(sorted(d.values())[:len(list(d.keys()))-K:])))
# Original solution
nk = list(map(int,input().split()))
a = list(map(int,input().split()))

sa = list(set(a))

if len(sa) > nk[1]:
	c = []
	for i in range(len(sa)):
		c.append(a.count(sa[i]))
		
	sortc = sorted(c, reverse = True)
	m = 0
	for i in range(nk[1]):
		m += sortc[i]
	ans = nk[0] - m
else:
	ans = 0

print(ans)


# Optimized solution
nk = list(map(int,input().split()))
a = list(map(int,input().split()))

cli = []
for i in range(nk[0]+1):
	cli.append(0)

for i in range(nk[0]):
	cli[a[i]] += 1

c = sorted(cli, reverse = True)

m = 0
for i in range(nk[1]):
	m += c[i]

ans = nk[0] - m
if ans < 0:
	ans = 0
	
print(ans)
# Original solution
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))

count = dict()
for i in a:
  count[i] = count.get(i, 0) + 1

ans = 0
while len(count) > k:
  key, value = min(list(count.items()), key=lambda x : x[1])
  del count[key]
  ans += value

print(ans)

# Optimized solution
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))

count = {}
for i in a:
  count[i] = count.get(i, 0) + 1

print((sum(sorted(count.values())[:-k])))
# Original solution
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))

A_dict = {str(i):0 for i in set(A)}
for a in A:
  A_dict[str(a)] += 1
del A
  
def get_A_key_from_value(dic, value):
  for i, j in list(dic.items()):
    if j == value:
      break
  return i
  
ans = 0
while True:
  if len(A_dict) <= K:
    break
  ans += min(A_dict.values())
  del A_dict[get_A_key_from_value(A_dict,min(A_dict.values()))]
print(ans)  

# Optimized solution
#読み込み
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
#処理回数
reduce_type = len(set(A)) - K
#削除する数の選定
A_dict = {str(i):0 for i in set(A)}
for a in A:
  A_dict[str(a)] += 1
del A
list_del_num = sorted(list(A_dict.values()))[:reduce_type]
#計算
ans = sum(list_del_num)
print(ans)
# Original solution
N,K=list(map(int,input().split()))
a=list(map(int,input().split()))
d=[0]*N
ans=0
for i in range(N):
    d[a[i]-1]+=1
d.sort(reverse=True)
while len(d)>K:
    if i!=0:
        ans += d.pop(K)
    else:
        break
print(ans)

# Optimized solution
N,K=list(map(int,input().split()))
a=list(map(int,input().split()))
d=[0]*N
ans=0
for i in range(N):
    d[a[i]-1]+=1
d.sort(reverse=True)
if len(d)>K:
    ans =sum(d[K:])
print(ans)
# Original solution
def resolve():
    # 整数 1 つ
    # n = int(input())
    # 整数複数個
    n, k = list(map(int, input().split()))
    # 整数 N 個 (改行区切り)
    # N = [int(input()) for i in range(N)]
    # 整数 N 個 (スペース区切り)
    A = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    # A = [list(map(int, input().split())) for i in range(H)]

    Unique = list(set(A))
    Dic = {x:A.count(x) for x in set(A)}

    if len(set(A)) <= k:
        print((0))
    else:
        Dicsort = sorted(list(Dic.items()), key=lambda x: x[1])
        cnt = 0
        for i in range(len(set(A)) - k):
            cnt += Dicsort[i][1]
        print(cnt)
resolve()

# Optimized solution
N,K = list(map(int,input().split()))
A = list(map(int,input().split()))

Ad = {x:0 for x in set(A)}
if len(set(A)) <= K:
    print((0))
else:
    count = 0
    for a in A:
        Ad[a] += 1
    Ad = sorted(list(Ad.items()), key=lambda x:x[1])
    for i in range(len(set(A))-K):
        count += Ad[i][1]
    print(count)
# Original solution
def resolve():
    # 整数 1 つ
    # n = int(input())
    # 整数複数個
    n, k = list(map(int, input().split()))
    # 整数 N 個 (改行区切り)
    # N = [int(input()) for i in range(N)]
    # 整数 N 個 (スペース区切り)
    A = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    # A = [list(map(int, input().split())) for i in range(H)]

    Unique = list(set(A))
    Dic = {x:0 for x in set(A)}

    if len(set(A)) <= k:
        print((0))
    else:
        for x in A:
            Dic[x] += 1
        Dicsort = sorted(list(Dic.items()), key=lambda x: x[1])

        cnt = 0
        for i in range(len(set(A)) - k):
            cnt += Dicsort[i][1]
        print(cnt)
resolve()

# Optimized solution
def resolve():
    # 整数 1 つ
    # n = int(input())
    # 整数複数個
    n, k = list(map(int, input().split()))
    # 整数 N 個 (改行区切り)
    # N = [int(input()) for i in range(N)]
    # 整数 N 個 (スペース区切り)
    A = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    # A = [list(map(int, input().split())) for i in range(H)]

    Dic = {x:0 for x in set(A)}
    if len(Dic) <= k:
        print((0))
    else:
        for i in A:
            Dic[i] += 1
        Dicsort = sorted(list(Dic.items()), key=lambda x: x[1])

        cnt = 0
        for j in range(len(Dic) - k):
            cnt += Dicsort[j][1]

        print(cnt)
resolve()
# Original solution
N,K = list(map(int,input().split()))
A =list(map(int,input().split()))

num = [0]*2000001

for i in range(N):
    num[A[i]] +=1

V = 2000001 - num.count(0)

if V <=K:
    print((0))
else:
    num.sort()
    num.reverse()
    print((sum(num[K:])))

# Optimized solution
N,K = list(map(int,input().split()))
A =list(map(int,input().split()))

num = [0]*(N+1)

for i in range(N):
    num[A[i]] +=1

V = N+1 - num.count(0)

if V <=K:
    print((0))
else:
    num.sort()
    num.reverse()
    print((sum(num[K:])))
# Original solution
import collections
n,k = (int(i) for i in input().split())
a = list(int(i) for i in input().split())
c = collections.Counter(a)
ct = 0
for i in range(k):
 try:
  ct += c.most_common()[i][1]
 except:
  break
ans = n-ct
if ans <0:
  ans = 0
print(ans)

# Optimized solution
import collections
n,k = (int(i) for i in input().split())
a = list(int(i) for i in input().split())
c = collections.Counter(a)
values,counts = list(zip(*c.most_common()))
if len(counts) >= k:
 ans = sum(counts[k:])
else:
 ans = 0

print(ans)
# Original solution
from collections import Counter, deque, defaultdict
n, k = list(map(int, input().split()))
A = list(map(int, input().split()))
t = defaultdict(int)
for x in A:
    t[x]+=1
B = []
for x in list(t.values()):
    B.append(x)
B.sort()
if(len(B)<=k):
    print((0))
    exit()
    
ans = 0
for i in range(0, len(B)):
    ans+=B[i]
    if len(B)-(i+1) <= k:
        break
print(ans)


# Optimized solution
from collections import Counter, deque, defaultdict
n, k = list(map(int, input().split()))
A = list(map(int, input().split()))
t = defaultdict(int)
for x in A:
    t[x]+=1
B = list(t.values())
B.sort()
if(len(B)<=k):
    print((0))
    exit()

ans = sum(B[:len(B)-k])
print(ans)
# Original solution
from collections import Counter as C

_, k = list(map(int, input().split()))
a = [int(i) for i in input().split()]

ans = 0
c = sorted(C(a).values())
while k < len(c):
    ans += c.pop(0)
else:
    print(ans)

# Optimized solution
from collections import Counter, deque

_, k = list(map(int, input().split()))
a = [int(i) for i in input().split()]

ans = 0
d = deque(sorted(Counter(a).values()))
while k < len(d):
    ans += d.popleft()
else:
    print(ans)
# Original solution
from collections import Counter, deque

_, k = list(map(int, input().split()))
a = [int(i) for i in input().split()]

ans = 0
d = deque(sorted(Counter(a).values()))
while k < len(d):
    ans += d.popleft()
else:
    print(ans)

# Optimized solution
from collections import Counter as C

_, k = list(map(int, input().split()))
a = [int(i) for i in input().split()]

c = list(C(a).values())
d = len(c) - k
if 0 < d:
    print((sum(sorted(c)[:d])))
else:
    print((0))
# Original solution
from collections import Counter

n, k = list(map(int, input().split()))
A = Counter([int(i) for i in input().split()]).most_common()

count = 0
if len(A) > k:
    for i in range(len(A) - k):
        count += A[k + i][1]
        
print(count)

# Optimized solution
from collections import Counter
N, K = list(map(int, input().split()))
A = Counter([int(i) for i in input().split()]).most_common()
cnt = 0
for a in A[K:]:
    cnt += a[1]
print(cnt)
# Original solution
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
set_A = set(A)
len_types = len(set_A)
memo = [0] * N
ans = 0

for num in set_A:
    count_num = A.count(num)
    memo[num-1] = count_num

memo.sort()

for i in memo[:N-K]:
    ans += i

# while len_types > K:
#     ans += heapq.heappop(memo)
#     len_types -= 1

print(ans)


# Optimized solution
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
memo = [0] * N
ans = 0

for a in A:
    memo[a-1] += 1
    
memo.sort()

for i in memo[:N-K]:
    ans += i

print(ans)
# Original solution
from collections import Counter

N, K = list(map(int, input().split()))
cnt = Counter(list(map(int, input().split())))
res = 0
l = len(cnt)
for i in range(l, K, -1):
    res += cnt.most_common(i)[-1][1]
print(res)

# Optimized solution
from collections import Counter

N, K = list(map(int, input().split()))
cnt = Counter(list(map(int, input().split())))
res = 0
l = len(cnt)
mc = cnt.most_common()
for i in range(l - 1, K - 1, -1):
    res += mc[i][1]
print(res)
# Original solution
from collections import Counter

n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
d = Counter(a)
d = d.most_common()
ans = 0

for i in range(len(d) - k):
    ans += d[-i - 1][1]

print(ans)

# Optimized solution
from collections import Counter

n, k = list(map(int, input().split()))
a = input().split()
d = sorted(Counter(a).values())
ans = 0

for i in range(len(d) - k):
    ans += d[i]

print(ans)
# Original solution
def main():
    n, k = list(map(int, input().split()))
    A = list(map(int, input().split()))

    res = 0
    balls = {}

    for ball in A:
        if ball in balls:
            balls[ball] += 1
        else:
            balls[ball] = 1
    
    delList = []
    bucket = [0 for _ in range(n+1)]

    for a in A:
        bucket[a] += 1
    
    for i in range(len(bucket)):
        if bucket[i] == 0:
            bucket[i] = 10**9
    
    for _ in range(len(set(A))):
        minBucket = min(bucket)
        minBucketIdx = bucket.index(minBucket)
        delList.append(minBucketIdx)
        bucket[minBucketIdx] = 10**9

    while len(delList) > k:
        res += balls[delList[0]]
        delList.pop(0)
    
    print(res)

if __name__ == '__main__':
    main()

# Optimized solution
def main():
    n, k = list(map(int, input().split()))
    A = list(map(int, input().split()))

    res = 0
    balls = {}
    bucket = [[] for _ in range(n+1)]

    for ball in A:
        if ball in balls:
            balls[ball] += 1
        else:
            balls[ball] = 1
    
    for key, value in list(balls.items()):
        bucket[value].append(key)

    for i in range(len(bucket)):
        for j in range(len(bucket[i])):
            if bucket[i] != [] and len(balls) > k:
                res += i
                balls.pop(bucket[i][j])

    print(res)

if __name__ == '__main__':
    main()
# Original solution
import queue
que = queue.PriorityQueue()
dic = {
        ord('r')+ord('g'): 'b',
        ord('g')+ord('b'): 'r',
        ord('b')+ord('r'): 'g',
        }
while True:
    s = input()
    if s=='0':
        break
    while not que.empty():
        que.get()
    cost = {}
    cost[s] = 0
    que.put((0, s))
    ans = -1
    while not que.empty():
        nn, ss = que.get()
        if all(e == ss[0] for e in ss):
            ans = nn
            break
        if cost[ss] < nn:
            continue
        for i in range(len(ss)-1):
            c0, c1 = ss[i], ss[i+1]
            if c0 != c1:
                code = dic[ord(c0)+ord(c1)]
                sa = ss[:i] + code*2 + ss[i+2:]
                if sa not in cost or nn+1 < cost[sa]:
                    cost[sa] = nn+1
                    que.put((nn+1, sa))
    print("NA" if ans<0 else ans)

# Optimized solution
import queue
dic = {
        'rg':'b', 'gr':'b',
        'gb':'r', 'bg':'r',
        'br':'g', 'rb':'g',
        }
while True:
    s = input()
    if s=='0':
        break
    que = queue.PriorityQueue()
    l = len(s)
    cost = {}
    cost[s] = 0
    que.put((0, s))
    ans = -1
    while not que.empty():
        nn, ss = que.get()
        if all(e == ss[0] for e in ss):
            ans = nn
            break
        if cost[ss] < nn:
            continue
        for i in range(l-1):
            cc = ss[i:i+2]
            if cc[0]!=cc[1]:
                code = dic[cc]
                sa = ss[:i] + code*2 + ss[i+2:]
                if sa not in cost or nn+1 < cost[sa]:
                    cost[sa] = nn+1
                    que.put((nn+1, sa))
    print("NA" if ans<0 else ans)