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)
import queue

dic = {

        'rg':'bb', 'gr':'bb',

        'gb':'rr', 'bg':'rr',

        'br':'gg', 'rb':'gg',

        }

while True:

    s = input()

    if s=='0':

        break

    que = queue.PriorityQueue()

    l = len(s)

    cost = {s: 0}

    que.put((0, s))

    aa = ['r'*l, 'g'*l, 'b'*l]

    ans = -1

    while not que.empty():

        nn, ss = que.get()

        if ss in aa:

            ans = nn

            break

        if cost[ss] < nn:

            continue

        for i in range(l-1):

            cc = ss[i:i+2]

            if cc[0]!=cc[1]:

                sa = ss[:i] + dic[cc] + 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)
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)

import queue

dic = {
    "rg": "bb",
    "gr": "bb",
    "gb": "rr",
    "bg": "rr",
    "br": "gg",
    "rb": "gg",
}
while True:
    s = input()
    if s == "0":
        break
    que = queue.PriorityQueue()
    l = len(s)
    cost = {s: 0}
    que.put((0, s))
    aa = ["r" * l, "g" * l, "b" * l]
    ans = -1
    while not que.empty():
        nn, ss = que.get()
        if ss in aa:
            ans = nn
            break
        if cost[ss] < nn:
            continue
        for i in range(l - 1):
            cc = ss[i : i + 2]
            if cc[0] != cc[1]:
                sa = ss[:i] + dic[cc] + 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)

-    "rg": "b", -    "gr": "b", -    "gb": "r", -    "bg": "r", -    "br": "g", -    "rb": "g", +    "rg": "bb", +    "gr": "bb", +    "gb": "rr", +    "bg": "rr", +    "br": "gg", +    "rb": "gg", -    cost = {} -    cost[s] = 0 +    cost = {s: 0} +    aa = ["r" * l, "g" * l, "b" * l] -        if all(e == ss[0] for e in ss): +        if ss in aa: -                code = dic[cc] -                sa = ss[:i] + code * 2 + ss[i + 2 :] +                sa = ss[:i] + dic[cc] + ss[i + 2 :]