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

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)

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)

-que = queue.PriorityQueue() -    ord("r") + ord("g"): "b", -    ord("g") + ord("b"): "r", -    ord("b") + ord("r"): "g", +    "rg": "b", +    "gr": "b", +    "gb": "r", +    "bg": "r", +    "br": "g", +    "rb": "g", -    while not que.empty(): -        que.get() +    que = queue.PriorityQueue() +    l = len(s) -        for i in range(len(ss) - 1): -            c0, c1 = ss[i], ss[i + 1] -            if c0 != c1: -                code = dic[ord(c0) + ord(c1)] +        for i in range(l - 1): +            cc = ss[i : i + 2] +            if cc[0] != cc[1]: +                code = dic[cc]