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++: #define _USE_MATH_DEFINES
#define MAX_N 1000000
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>

using namespace std;

typedef long long ll;
typedef pair<int,string> P;

static const double eps = 1e-8;


static const char a[] = {'r','g','b'};

bool checkColor(const string& str){

	bool res = false;
	for(int i=0;i<3;i++){
		if(count(str.begin(),str.end(),a[i]) == str.size()) res=true;
	}

	return res;
}

int changeColor(string str,int cost,map<string,int>& visited){

	if(checkColor(str)) return 0;

	priority_queue<P,vector<P>,greater<P> > que;
	que.push(P(0,str));

	while(!que.empty()){
		int cost = que.top().first;
		string now = que.top().second;

		que.pop();
		for(int i=0;i+1<now.size();i++){
			string tmp = now;
			if(now[i] != now[i+1]){
				for(int j=0;j<3;j++){
					if(a[j] != now[i] && a[j] != now[i+1]){
						tmp[i] = a[j];
						tmp[i+1] = a[j];
						break;
					}
				}

				if(visited.find(tmp) == visited.end()) visited[tmp] = cost + 1;
				else if(visited[tmp] <= cost+1) continue;

				if(checkColor(tmp)) return cost+1;
				que.push(P(cost+1,tmp));
			}
		}
	}

	return -1;

}

int main(){
	string str;

	while(cin>>str){
		if(str.size() == 1 && str[0] == '0') break;
		map<string,int> visited;
		visited[str] = 0;

		int res = changeColor(str,0,visited);

		if(res==-1) printf("%s\n","NA");
		else printf("%d\n",res);
	}
}

C++: #include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<numeric>
#include<algorithm>
#include<bitset>
#include<complex>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
#define mp make_pair

template<class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }
int in() { int x; scanf("%d", &x); return x; }

int res[11][180000];

int p(int n){
	if(n==0) return 1;
	return 3*p(n-1);
}

priority_queue<pint,vector<pint>,greater<pint> > bfs;
int i;

void g(pint a){
	int j;
	for(j=0;j<i-1;j++){
		if(a.second%p(j+1)/p(j)==a.second%p(j+2)/p(j+1)){
			int k=a.second%p(j+1)/p(j);
			int l=a.second;
			l-=k*p(j)+k*p(j+1);
			if(k==0){
				bfs.push(mp(a.first+1,l+p(j)+2*p(j+1)));
				bfs.push(mp(a.first+1,l+2*p(j)+p(j+1)));
			}
			if(k==1){
				bfs.push(mp(a.first+1,l+2*p(j+1)));
				bfs.push(mp(a.first+1,l+2*p(j)));
			}
			if(k==2){
				bfs.push(mp(a.first+1,l+p(j+1)));
				bfs.push(mp(a.first+1,l+p(j)));
			}
		}
	}
	return;
}

int main() {
	memset(res,-1,sizeof(res));
	for(i=2;i<=10;i++){
		int j,k=0;
		while(!bfs.empty())bfs.pop();
		for(j=0;j<i;j++)k+=p(j)*0;
		res[i][k]=0;
		g(mp(0,k));
		k=0;
		for(j=0;j<i;j++)k+=p(j)*1;
		res[i][k]=0;
		g(mp(0,k));
		k=0;
		for(j=0;j<i;j++)k+=p(j)*2;
		res[i][k]=0;
//cout<<k<<endl;
		g(mp(0,k));
		while(!bfs.empty()){
			pint buf;
			buf=bfs.top();
			bfs.pop();
//cout<<buf.first<<" "<<buf.second<<endl;
			if(res[i][buf.second]!=-1&&res[i][buf.second]<=buf.first)continue;
			res[i][buf.second]=buf.first;
			g(buf);
		}
	}
//for(i=2;i<=10;i++){
//	int j;
//	for(j=0;j<p(i);j++){
//		int l;
//		for(l=0;l<i;l++){
//			if(j/p(l)%3==0)cout<<"r";
//			if(j/p(l)%3==1)cout<<"b";
//			if(j/p(l)%3==2)cout<<"g";
//		}
//		cout<<" "<<res[i][j]<<endl;
//	}
//}
	string str;
	while(cin>>str,str!="0"){
		int k=0;
		int j;
		for(j=0;j<str.size();j++){
			if(str[j]=='r')k=k*3+0;
			if(str[j]=='b')k=k*3+1;
			if(str[j]=='g')k=k*3+2;
		}
		if(res[str.size()][k]>=0)cout<<res[str.size()][k]<<endl;
		else cout<<"NA\n";
	}
	return 0;
}