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 <utility>
#include <string>
#include <queue>
#include <climits>
#include <vector>
using namespace std;

#define _gp(l) const auto gcu{getchar##l}; const auto pcu{putchar##l}
#ifdef __linux
_gp(_unlocked);
#else
_gp();
#endif
#define _DEF(r, n, ...) inline r n(__VA_ARGS__) noexcept
#define _T template <typename T>
#define _HT template <typename H,typename... T>
#define _OP(t) inline operator t()
struct _in {
#ifdef _GLIBCXX_STRING
	_OP(string){string s;for(char c;c=gcu(),c!=' '&&c!='\n';)s+=c;return s;}
#define _S
#endif
	_OP(char){char c=gcu();gcu();return c;}
	_OP(double){double d; scanf("%lf",&d); gcu();return d;}
	_T _OP(T){T n{},m{1},c;if((c=gcu())=='-')m=-1,c=gcu();do{n=10*n+(c-'0'),c=gcu();}while(c>='0'&&c<='9');return m*n;}
} in;
#define _SCAN(...) _DEF(bool,scan,__VA_ARGS__)
#ifdef _S
_SCAN(string &o) {int c{gcu()};if(c==EOF)return false;else{ungetc(c,stdin);string t=move(in);o=t;return true;}}
#endif
_T _SCAN(T &o) {int c{gcu()};return c==EOF?false:(ungetc(c,stdin),o=in,true);}
_HT _SCAN(H &h,T&&... t){return scan(h)&&scan(t...);}
#define _OUT(...) _DEF(void,out,__VA_ARGS__)
#define _OUTL(...) _DEF(void,outl,__VA_ARGS__)
_OUT(bool b){pcu('0'+b);}
_OUT(const char *s){while(*s)pcu(*s++);}
_OUT(char c){pcu(c);}
#ifdef _S
_OUT(string &s){for(char c:s)pcu(c);}
#endif
_T _OUT(T n){static char b[20];char *p=b;T m=n<0?pcu('-'),-1:1;
	if(!n)*p++='0';else while(n)*p++=(char)(n%10*m+'0'),n/=10;while(p!=b)pcu(*--p);}
	_OUTL(){out('\n');}
#ifdef _GLIBCXX_VECTOR
	_T _OUT(vector<T> &v){for(T &x:v)out(&x == &v[0]?"":" "),out(x);}
#endif
	_HT _OUT(H &&h, T... t){out(h);out(t...);}
	template <typename... T> _OUTL(T... t){out(t...);outl();}
	struct range{
		int e,b=0,s=1;range(int _b,int _e,int _s):e(_e),b(_b),s(_s){} range(int _b,int _e): e(_e), b(_b){} range(int _e):e(_e){}
		struct it{int v,s; it(int _v,int _s):v(_v),s(_s){} operator int()const{return v;} operator int&(){return v;}int operator*()const{return v;}
			it& operator++(){v+=s;return *this;} }; it begin(){return {b,s};} it end(){return {e,s};}};
#define times(i,n) for(int i=n;i;i--)

struct N {
	int s, n;
};

bool all(int n) {
	int c = n & 3;
	n >>= 2;
	for (; n; n >>= 2)
		if ((n & 3) != c)
			return false;
	return true;
}

int main() {
	for (;;) {
		string s = in;
		if (s == "0")
			return 0;
		vector<bool> m(1 << s.size() * 2);
		int t {};
		for (char c: s)
			t = t << 2 | (c == 'r' ? 1 : c == 'g' ? 2 : 3);
		m[t] = true;
		queue<N> q;
		q.push({t, 0});
		[&] {
			while (!q.empty()) {
				N f {q.front()};
				q.pop();
				if (all(f.s)) {
					outl(f.n);
					return;
				}
				for (int i: range(1, s.size())) {
					int x = (i - 1) * 2,
						m0 = f.s >> x & 3,
						m1 = f.s >> i * 2 & 3;
					if (m0 != m1) {
						int g = m0 ^ m1,
							t = (f.s & ~(15 << x)) | (g | g << 2) << x;
						if (!m[t]) {
							m[t] = true;
							q.push({t, f.n + 1});
						}
					}
				}
			}
			outl("NA");
		}();
	}
}

C++: #include<iostream>
#include<string>
#include<queue>
#include<map>
using namespace std;
int main(){

  string s,str,col[3];
  queue<string> que;
  map<string,int> mp;
  int flag;
  while(1){
    cin >> s;
    if(s == "0") break;
    flag = 1;
    que.push(s);
    mp[s] = 0;
    for(int i=0;i<3;i++) col[i] = "";
    for(int i=0;i<s.size();i++){
      col[0] += "r";
      col[1] += "b";
      col[2] += "g";
    }
    while(!que.empty()){
      if(que.front()==col[0]){
	cout << mp[col[0]] << endl;
	flag--;
	break;
      }
      if(que.front()==col[1]){
	cout << mp[col[1]] << endl;
	flag--;
	break;
      }
      if(que.front()==col[2]){
	cout << mp[col[2]] << endl;
	flag--;
	break;
      }
      
      for(int i=0;i<s.size()-1;i++){
	str = que.front();
	if(str[i] != str[i+1]){
	  if(str[i] != 'r' && str[i+1] != 'r'){
	    str[i] = 'r';
	    str[i+1] = 'r';
	  } else if(str[i] != 'b' && str[i+1] != 'b'){
	    str[i] = 'b';
	    str[i+1] = 'b';
	  }else if(str[i] != 'g' && str[i+1] != 'g'){
	    str[i] = 'g';
	    str[i+1] = 'g';
	  }
	  if(mp.find(str) == mp.end()){
	    que.push(str);
	    mp[str] = mp[que.front()]+1;
	  }
	}
      }
      que.pop();
    }
    while(!que.empty()) que.pop();
    if(flag) cout << "NA" << endl;
  }
  return (0);
}