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 <algorithm>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <cassert>
#include <functional>

using namespace std;

#define LOG(...) printf(__VA_ARGS__)
//#define LOG(...)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).rbegin(),(c).rend())
#define CLR(a) memset((a), 0 ,sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int dx[] = {-1,0,1,0}; const int dy[] = {0,1,0,-1};
int worm[4][4][4][4][4][4][4][4][4][4];

int main() {
	fill_n((int *)worm, 4*4*4*4*4*4*4*4*4*4, -1);

	FOR(n, 2, 10 + 1){
		queue<vi> que;
		REP(c, 3){
			vi w(10, 0);
			REP(i, n){
				w[i] = c+1;
			}
			worm[w[0]][w[1]][w[2]][w[3]][w[4]][w[5]][w[6]][w[7]][w[8]][w[9]] = 0;
			que.push(w);
		}
		que.push({});

		int step = 1;
		while(1){
			vi p = que.front(); que.pop();
			if(p.size() == 0){
				if(que.empty())
					break;
				step ++;
				que.push(p);
			}
			FOR(i, 1, p.size()){
				if(p[i-1] != p[i]) continue;
				if(p[i] == 0)continue;
				vi w1 = p;
				w1[i-1] = p[i-1] % 3 + 1;
				w1[i  ] = (p[i-1] + 1) % 3 + 1;
				vi w2 = p;
				w2[i-1] = (p[i-1] + 1) % 3 + 1;
				w2[i  ] = p[i-1]% 3 + 1;

				if (worm[w1[0]][w1[1]][w1[2]][w1[3]][w1[4]][w1[5]][w1[6]][w1[7]][w1[8]][w1[9]] == -1){
					worm[w1[0]][w1[1]][w1[2]][w1[3]][w1[4]][w1[5]][w1[6]][w1[7]][w1[8]][w1[9]] = step;
					que.push(w1);
				}
				if (worm[w2[0]][w2[1]][w2[2]][w2[3]][w2[4]][w2[5]][w2[6]][w2[7]][w2[8]][w2[9]] == -1){
					worm[w2[0]][w2[1]][w2[2]][w2[3]][w2[4]][w2[5]][w2[6]][w2[7]][w2[8]][w2[9]] = step;
					que.push(w2);
				}
			}
		}
	}

	string wm;
	while(cin >>wm, wm != "0"){
		vi w(10, 0);
		REP(i, wm.length()){
			w[i] = wm[i] % 3 + 1;
		}

		if(worm[w[0]][w[1]][w[2]][w[3]][w[4]][w[5]][w[6]][w[7]][w[8]][w[9]] == -1)
			cout << "NA" << endl;
		else
			cout << worm[w[0]][w[1]][w[2]][w[3]][w[4]][w[5]][w[6]][w[7]][w[8]][w[9]] << endl;
	}
}

C++: #include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <sstream>
#include <cassert>
#include <list>
using namespace std;
static const double EPS = 1e-8;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PI;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define SZ(a) (int(a.size()))
#define F first
#define S second
const double pi=acos(-1);
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};

void solve(string s){
  set<string> app;

  queue<pair<int,string> > q;
  q.push(mp(0,s));
  while(!q.empty()){
    int cc=q.front().F;
    s=q.front().S;
    q.pop();
    if(app.count(s))continue;
    app.insert(s);
    bool end=true;
    rep(i,SZ(s)-1){
      if(s[i]!=s[i+1]){
        end=false;
        break;
      }
    }

    if(end){
      cout<<cc<<endl;
      return;
    }

    rep(i,SZ(s)-1){
      if(s[i]==s[i+1])continue;
      string t=s;
      char a=min(s[i],s[i+1]);
      char b=max(s[i],s[i+1]);

      if(a!='r' && b!='r')t[i]=t[i+1]='r';
      else if(a!='g' && a!='g')t[i]=t[i+1]='g';
      else t[i]=t[i+1]='b';
      if(app.count(t))continue;
      q.push(mp(cc+1,t));
    }
  }
  cout<<"NA"<<endl;
}

main(){
  string s;
  while(cin>>s,s!="0")
    solve(s);
}