Go: package main

import (
    "bufio"
    "os"
    "fmt"
)

var sc = bufio.NewScanner(os.Stdin)

/**************  Cell  *****************/
type Cell struct {
    item interface{}
    next *Cell
    prev *Cell
}

func NewCell(x interface{}, ne *Cell, pr *Cell) *Cell {
    newCp := new(Cell)
    newCp.item = x
    newCp.next = ne
    newCp.prev = pr
    return newCp
}
/************  End Cell  ***************/

/**************  Queue  ****************/
type Queue struct {
    size int
    front *Cell
    rear *Cell
}

func NewQueue() *Queue {
    return new(Queue)
}

func (q *Queue) Push(x interface{}) {
    newNode := NewCell(x, nil, nil)
    if q.size == 0 {
        q.front = newNode
        q.rear = newNode
    } else {
        newNode.prev = q.rear
        q.rear.next = newNode
        q.rear = newNode
    }
    q.size++
}

func (q *Queue) PopLeft() interface{} {
    if q.size == 0 {
        return nil
    } else {
        x := q.front.item
        if q.size == 1 {
            q.front = nil
            q.rear = nil
        } else {
            q.front = q.front.next
            q.front.prev = nil
        }
        q.size--
        return x
    }
}

func (q *Queue) IsEmpty() bool {
    return q.size == 0
}

func (q *Queue) Length() int {
    return q.size
}

type State struct {
    color string
    cnt int
}

func main() {
    for {
        sc.Scan()
        init := sc.Text()
        if init == "0" {
            break
        }
        bfs(init)
    }
}

func bfs(init string) {
    dic := make(map[string]int)
    que := NewQueue()
    que.Push(State{init, 0})
    length := len(init)
    isSolved := false
    for !que.IsEmpty() {
        state := que.PopLeft().(State)
        _, ok := dic[state.color]
        if ok {
            continue
        } else {
            dic[state.color] = state.cnt
        }

        if isSingleColor(state.color) {
            fmt.Println(state.cnt)
            isSolved = true
            break
        }

        for i := 0;i < length - 1; i++ {
            color1, color2 := string(state.color[i]), string(state.color[i + 1])
            if color1 != color2 {
                color3 := other(color1, color2)
                if i <= length - 2 {
                    que.Push(State{state.color[:i] + color3 + state.color[i + 2:], state.cnt + 1})
                } else {
                    que.Push(State{state.color[:i] + color3, state.cnt + 1})
                }
            }
        }
    }
    if !isSolved {
        fmt.Println("NA")
    }
}

func other(color1, color2 string) string {
    if color1 == "r" {
        if color2 == "g" {
            return "bb"
        } else if color2 == "b" {
            return "gg"
        }
    } else if color1 == "g" {
        if color2 == "r" {
            return "bb"
        } else if color2 == "b" {
            return "rr"
        }
    } else if color1 == "b" {
        if color2 == "r" {
            return "gg"
        } else if color2 == "g" {
            return "rr"
        }
    }
    return ""
}

func isSingleColor(color string) bool {
    for _, c := range color {
        if string(c) != string(color[0]) {
            return false
        }
    }
    return true
}

C++: 
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <functional>
#include <queue>
#include <stack>
#include <cmath>
#include <iomanip>
 
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define CLR(a) memset((a), 0 ,sizeof(a))
#define MCLR(a) memset((a), -1 ,sizeof(a))
#define SZ(a) (sizeof(a))
#define FILL(a,v) fill((int*)a,(int*)(a+(SZ(a)/SZ(*(a)))),v)
#define dump(x)  cerr << #x << " = " << (x) << endl

bool cheak(int x,int y,int xMax,int yMax)
{return x >= 0 && y >= 0 && xMax > x && yMax > y;}
const int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
const int INF = 2147483647;
typedef pair<int,int> P;
typedef long long ll;
typedef unsigned long long ull;

//???????????¢?´¢
struct Bfs
{
	set<string> memo;
	int search(string s)
	{
		queue<string> que;
		queue<int>    time;
		que.push(s);
		time.push(0);
		memo.insert(s);
		while(que.size())
		{
			string now = que.front();que.pop();
			int anstime = time.front();time.pop();
			//??????
			
			bool end = true;
			REP(i,now.size()-1)
			if(now[i] != now[i+1])
			end = false;
			if(end)return anstime; 
			//

			REP(i,now.size()-1)
			{
				string ts = now;
				char c0 = now[i];
				char c1 = now[i+1];
				char sc;
				if(c0 != c1)
				{
					if(c0 != 'b' && c1 != 'b')
						sc = 'b';
					if(c0 != 'r' && c1 != 'r')
						sc = 'r';
					if(c0 != 'g' && c1 != 'g')
						sc = 'g';
					
					ts[i] = sc;ts[i+1] = sc;
					if(!memo.count(ts))
					{
						memo.insert(ts);
						que.push(ts);
						time.push(1+anstime);
					}
				}
			}
		}
		return -1;
	}
};

int main()
{
	string str;
	while(cin >> str && str != "0")
	{
		Bfs bfs;
		int ans = bfs.search(str);
		if(ans == -1)
			cout << "NA" << endl;
		else
			cout <<  ans << endl;
	}
	return 0;
}


//????¬????????????????????????¨?????????
/*
	REP(i,mx)
	{
		REP(j,my)
		cout << n[i][j];
		cout << endl;
	}
	cout << endl;
*/

C++: //01 = r, 10 = g, 11 = b

#include<iostream>
#include<queue>
#include<set>
#include<string>
#include<map>
#include<cmath>
using namespace std;

#define P pair<int, int>

int makeWormBit(string str);
void makeEnd(int size);
bool checkEnd(int n);
int changeColor(int n, int i, int size);
int searchChangeColor(int n, int i, int mask);
int makeResetMask(int size, int mask);

int endColor[3];

int main(){
    string str;
    while(cin >>str){
        if(str[0] == '0') break;
        int bw = makeWormBit(str), deep = 1;
        queue<P> q;
        set<int> s;
        q.push( make_pair(0, bw) );
        s.insert(bw);
        makeEnd(str.size());
        while(!q.empty()){
            P tmp = q.front();
            if(checkEnd(tmp.second)){
                cout <<tmp.first <<endl;
                break;
            } else{
                for(int i = 0; i < str.size() - 1; i++){
                    int t = changeColor(tmp.second, i, str.size());
                    if(s.find(t) == s.end()){
                        q.push( make_pair(tmp.first + 1, t) );
                        s.insert(t);
                    }
                }
            }
            q.pop();
        }
        if(q.empty()) cout <<"NA" <<endl;
    }
    return 0;
}

int makeWormBit(string str){
    int ret = 0;
    for(int i = 0; i < str.size(); i++){
        ret = ret << 2;
        if(str[i] == 'r') ret |= 1;
        else if(str[i] == 'g') ret |= 2;
        else if(str[i] == 'b') ret |= 3;
    }
    return ret;
}
bool checkEnd(int n){
    bool ret = false;
    for(int i = 0; i < 3; i++){
        if(endColor[i] == n){
            ret = true;
            break;
        }
    }
    return ret;
}
int changeColor(int n, int i, int size){
    int ret = n, mask = 15 << (i * 2), resetMask = makeResetMask(size, mask), color = searchChangeColor(n, i, mask);
    ret &= resetMask;
    ret |= (color << (i * 2));
    return ret;
}

void makeEnd(int size){
    int dx[] = {1, 2, 3}, ans;
    for(int i = 0; i < 3; i++){
        ans = 0;
        for(int j = 0; j < size; j++){
            ans = ans << 2;
            ans |= dx[i];
        }
        endColor[i] = ans;
    }
}

int searchChangeColor(int n, int i, int mask){
    int strc[] = {5, 10, 15, 6, 7, 9, 11, 13, 14}, strret[] = {5, 10, 15, 15, 10, 15, 5, 10, 5};
    int c = (n & mask), ret;
    c = c >> (i * 2);
    for(int i = 0; i < 9; i++){
        if(c == strc[i]) ret = strret[i];
    }
    return ret;
}

int makeResetMask(int size, int mask){
    int ret = 1 << (size * 2);
    ret--;
    ret ^= mask;
    return ret;
}