rgb = set(["r","g","b"])

while 1:

	worm = input()

	if worm == "0": break

	n = len(worm)

	L = 1

	cnt = flag = 0

	queset = set([worm])

	ref = set()

	while 1:

		que = list(queset)

		queset = set()

		for Worm in que:

			if len(set(Worm)) == 1:

				flag = 1

				break

			for i in range(n-1):

				if Worm[i] != Worm[i+1]:

					nextclr = list(rgb-set(Worm[i:i+2]))[0]

					worm = Worm[:i] + 2*nextclr + Worm[i+2:]

					queset.add(worm)

		queset = queset - ref

		ref = ref|queset

		L = len(queset)

		if flag: break

		cnt += 1

		if cnt > 15: break

	print(cnt if flag else "NA")
dic = {"r":1,"g":2,"b":3}

rgb = ["r","g","b"]

while 1:

	worm = input()

	if worm == "0": break

	n = len(worm)

	ref = ["r"*n,"g"*n,"b"*n]

	cnt = flag = 0

	queset = set([worm])

	done = set()

	while 1:

		que = list(queset)

		queset = set()

		for Worm in que:

			if Worm in ref:

				flag = 1

				break

			for i in range(n-1):

				if Worm[i] != Worm[i+1]:

					nextclr = rgb[5-dic[Worm[i]]-dic[Worm[i+1]]]

					queset.add(Worm[:i] + 2*nextclr + Worm[i+2:])

		if flag or cnt > 14: break

		cnt += 1

		queset -= done

		done |= queset

	print(cnt if flag else "NA")
rgb = set(["r", "g", "b"])
while 1:
    worm = input()
    if worm == "0":
        break
    n = len(worm)
    L = 1
    cnt = flag = 0
    queset = set([worm])
    ref = set()
    while 1:
        que = list(queset)
        queset = set()
        for Worm in que:
            if len(set(Worm)) == 1:
                flag = 1
                break
            for i in range(n - 1):
                if Worm[i] != Worm[i + 1]:
                    nextclr = list(rgb - set(Worm[i : i + 2]))[0]
                    worm = Worm[:i] + 2 * nextclr + Worm[i + 2 :]
                    queset.add(worm)
        queset = queset - ref
        ref = ref | queset
        L = len(queset)
        if flag:
            break
        cnt += 1
        if cnt > 15:
            break
    print(cnt if flag else "NA")

dic = {"r": 1, "g": 2, "b": 3}
rgb = ["r", "g", "b"]
while 1:
    worm = input()
    if worm == "0":
        break
    n = len(worm)
    ref = ["r" * n, "g" * n, "b" * n]
    cnt = flag = 0
    queset = set([worm])
    done = set()
    while 1:
        que = list(queset)
        queset = set()
        for Worm in que:
            if Worm in ref:
                flag = 1
                break
            for i in range(n - 1):
                if Worm[i] != Worm[i + 1]:
                    nextclr = rgb[5 - dic[Worm[i]] - dic[Worm[i + 1]]]
                    queset.add(Worm[:i] + 2 * nextclr + Worm[i + 2 :])
        if flag or cnt > 14:
            break
        cnt += 1
        queset -= done
        done |= queset
    print(cnt if flag else "NA")

-rgb = set(["r", "g", "b"]) +dic = {"r": 1, "g": 2, "b": 3} +rgb = ["r", "g", "b"] -    L = 1 +    ref = ["r" * n, "g" * n, "b" * n] -    ref = set() +    done = set() -            if len(set(Worm)) == 1: +            if Worm in ref: -                    nextclr = list(rgb - set(Worm[i : i + 2]))[0] -                    worm = Worm[:i] + 2 * nextclr + Worm[i + 2 :] -                    queset.add(worm) -        queset = queset - ref -        ref = ref | queset -        L = len(queset) -        if flag: +                    nextclr = rgb[5 - dic[Worm[i]] - dic[Worm[i + 1]]] +                    queset.add(Worm[:i] + 2 * nextclr + Worm[i + 2 :]) +        if flag or cnt > 14: -        if cnt > 15: -            break +        queset -= done +        done |= queset