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 <iostream>
#include <algorithm>
#include <string>

using namespace std;

bool dfs(string str, int c)
{
	bool f = true;
	for(int i = 1; i < str.size(); i++){
		if(str[0] != str[i]){
			f = false;
			break;
		}
	}

	if(f){
		return f;
	}
	if(c == 0){
		return f;
	}
	
	char s, t, u;
	for(int i = 0; i < str.size()-1; i++){
		if(str[i] != str[i+1]){
			s = str[i];
			t = str[i+1];
			if((s == 'r' && t == 'b') || (s == 'b' && t == 'r')){
				u = 'g';
			} else if((s == 'r' && t == 'g') || (s == 'g' && t == 'r')){
				u = 'b';
			} else {
				u = 'r';
			}
			str[i] = str[i+1] = u;
			f = dfs(str, c-1);
			if(f){
				break;
			}
			str[i] = s;
			str[i+1] = t;
		}
	}
	
	return f;
}

int main()
{
	int t;
	string str;
	
	while(cin>>str){
		if(str == "0"){
			break;
		}
		
		for(t = 0; t <= 10; t++){
			if(dfs(str, t)){
				break;
			}
		}
		
		if(t > 10){
			cout << "NA" << endl;
		} else {
			cout << t << endl;
		}
	}
	
	return 0;
}

C++: #include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <iterator>
#include <map>
#include <set>
using namespace std;
typedef pair<vector<char>, int> VCI;
bool check(vector<char> worm){
  for(int i = 1; i < worm.size(); ++i){
    if(worm[0] != worm[i]){
      return false;
    }
  }
  return true;
}
map<pair<char, char>, char> table;
int bfs(string s){
  vector<char> worm;
  copy(s.begin(), s.end(), back_inserter(worm));
  int N = worm.size();
  queue<VCI> q;
  set<vector<char> > visited;
  q.push(make_pair(worm, 0));
  while(!q.empty()){
    VCI vci = q.front(); q.pop();
    vector<char> w = vci.first;
    int step = vci.second;
    if(check(w)){
      return step;
    }
    if(visited.find(w) != visited.end()){
      continue;
    }
    visited.insert(w);
    for(int i = 0; i < N-1; ++i){
      if(w[i] == w[i+1]){
        continue;
      }
      vector<char> nw;
      copy(w.begin(), w.end(), back_inserter(nw));
      nw[i] = nw[i+1] = table[make_pair(nw[i], nw[i+1])];
      q.push(make_pair(nw, step+1));
    }
  }
  return -1;
}

int main(){
  table[make_pair('r', 'b')] = table[make_pair('b', 'r')] = 'g';
  table[make_pair('r', 'g')] = table[make_pair('g', 'r')] = 'b';
  table[make_pair('b', 'g')] = table[make_pair('g', 'b')] = 'r';
  string s;
  while(true){
    cin >> s;
    if(s == "0"){
      break;
    }
    int ans = bfs(s);
    if(ans == -1){
      cout << "NA" << endl;
    }
    else{
      cout << bfs(s) << endl;
    }
  }
  return 0;
}

C++: #include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;

#define NA 10000000

string str;

char rgb(char v1, char v2)
{
  bool r, g, b;
  r = v1 == 'r' || v2 == 'r';
  b = v1 == 'b' || v2 == 'b';
  g = v1 == 'g' || v2 == 'g';
  
  if(!r)
    return 'r';
  if(!b)
    return 'b';
  return 'g';
}
int dfs(string s, bool isFirst, int n)
{
  int ans = 10000000;
  bool isEnd = true;

  //cout << "s: "<< s << endl;

  if(n > 10)
    return NA;
  if(str == s && !isFirst)
    return ans;
  for(int i = 0; i < s.length(); i++)
    isEnd &= s[0] == s[i];
  if(isEnd)
    return n;

  for(int i = 0; i < s.length() - 1; i++)
  {
    //cout << i << endl;
    if(s[i] != s[i + 1])
    {
      char c1 = s[i], c2 = s[i + 1];
      
      char c = rgb(s[i], s[i + 1]);
      //cout << c1 << c2;
      s[i] = s[i + 1] = c;
      ans = min(ans, dfs(s, false, n + 1));
      s[i] = c1;
      s[i + 1] = c2;
    }
  }

  return ans;
}


int main()
{
  while(1)
  {
    cin >> str;
    if(str[0] == '0')
      break;
    int a = dfs(str, true, 0);
    if(a == NA)
      cout << "NA\n";
    else
      cout << a << endl;
  }
}