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 <string>
#include <queue>
#include <vector>
#include <set>

using namespace std;

// テァツオツづ、ツコツ?ァツ環カテヲツ?凝」ツ?凝・ツ按、テ・ツョツ堙」ツ?凖」ツつ?
inline bool ok(const string & v){
    for (int i = 1; i < v.size(); i++){
        if (v[i] != v[0]) return false;
    }
    return true;
};

// 3ティツ可イテ」ツ?ョテ」ツ??」ツ?。ティツ可イa,ティツ可イbテ」ツ?ョテ」ツ?ゥテ」ツ?。テ」ツつ嘉」ツ?ァテ」ツつづ」ツ?ェテ」ツ??ィツ可イテ」ツつ津ィツソツ氾」ツ??
inline char other(char a, char b){
    if (a>b)swap(a, b);
    if (a == 'g' && b == 'r'){
        return 'b';
    }
    if (a == 'b' && b == 'g'){
        return 'r';
    }
    if (a == 'b' && b == 'r'){
        return 'g';
    }
    // テ・ツ?ィテ」ツ?ヲテ」ツ?ョifテ」ツ?ォテ・ツシツ陛」ツ?」テ」ツ?凝」ツ?凝」ツつ嘉」ツ?ェテ」ツ??」ツ?ョテ」ツ?ッテヲツ伉偲」ツつ嘉」ツ?凝」ツ?ォテ・ツ、ツ嘉」ツ?ェテ」ツ?ョテ」ツ?ァtry-catchテァツ?。テ」ツ?療」ツ?ァテ、ツセツ凝・ツ、ツ姪」ツつ津ヲツ環陛」ツ?津」ツつ?
    // テ」ツ?禿」ツ??」ツ?凖」ツつ凝」ツ?ィテ」ツつクテ」ツδ」テ」ツδε」ツつクテ」ツ?ァWAテ」ツ?ァテ」ツ?ッテ」ツ?ェテ」ツ?蹴Eテ」ツ?ォテ」ツ?ェテ」ツつ凝」ツ?ョテ」ツ?ァテ」ツδ?」ツδ静」ツδε」ツつーテ」ツ?療」ツつ?」ツ?凖」ツ??
    // Cティツィツ?ィツェツ榲」ツ?ァテ」ツ?ッassertテ」ツ?古、ツスツソテ」ツ?暗」ツつ?
    throw "illigal char";
}

// テ」ツつュテ」ツδ・テ」ツδシテ」ツ?ォテ・ツ?・テ」ツつ古」ツつ凝ァツ環カテヲツ?凝」ツ?ョテ・ツ楪?
struct state {
    string str;
    int n;
};

int main(){
    string s;
    while (cin >> s, s != "0"){
        queue<state> q;
        // テ」ツ?凖」ツ?ァテ」ツ?ォティツィツェテ」ツつ古」ツ?淌ァツ環カテヲツ?凝」ツつ津ヲツ?シテァツエツ催」ツ?凖」ツつ虐et テ・ツ按敕」ツつ?」ツ?ッテァツゥツコ
        set<string> dp;
        // テ・ツ按敕ヲツ慊淌ァツ環カテヲツ?凝」ツつ智ueueテ」ツ?ォテ・ツ?・テ」ツつ古」ツつ?
        q.push({ s, 0 });

        int ans = -1;
        while (q.size()){
            // staテ」ツ?繋ueueテ」ツ?ョテ、ツクツ?ァツ閉ェテ、ツクツ甘」ツ?ョテァツ環カテヲツ?凝」ツつ津、ツサツ甘」ツ?ョテァツ環カテヲツ?凝」ツ?ォテ」ツ?療ッツシツ繋ueueテ」ツ?凝」ツつ嘉・ツ?コテ」ツ??
            state sta = q.front();
            q.pop();
            string & sv = sta.str;

            // setテ」ツ?ォテ、ツサツ甘」ツ?ョテァツ環カテヲツ?凝」ツつ津・ツ?・テ」ツつ古」ツつ暗」ツ??」ツ?ィティツゥツヲテ」ツ?ソテ」ツつ凝ッツシツ?
            // autoテ」ツ?ォテ」ツ?、テ」ツ??」ツ?ヲティツゥツウテ」ツ?療」ツ?湘」ツ?ッテヲツ慊?・ツセツ古」ツ?ョテ」ツつウテ」ツδ。テ」ツδウテ」ツδ暗」ツ?ォ
            auto pr = dp.insert(sv);
            if (!pr.second){
                // テ、ツサツ甘」ツ?ョテァツ環カテヲツ?凝」ツ?茎etテ」ツ?ォテヲツ猟「テ」ツ?ォテ・ツ?・テ」ツ?」テ」ツ?ヲテ」ツ??」ツ?淌」ツ?淌」ツつ（nsertテ」ツ?ォテ・ツ、ツアテヲツ閉療」ツ?療」ツ?淌ッツシツ?
                // テ」ツ?、テ」ツ?セテ」ツつ甘ッツシツ古ゥツ?偲・ツ篠サテ」ツ?ョテ」ツδォテ」ツδシテ」ツδ療」ツ?ァテァツ「ツコティツェツ催ヲツクツ暗」ツ?ソテ」ツ?ョテ」ツ?淌」ツつ?ッツシツ古」ツ?禿」ツ?ョテァツ環カテヲツ?凝、ツサツ・テゥツ卍催」ツつ津ヲツ篠「テァツエツ「テ」ツ?凖」ツつ凝・ツソツ?ィツヲツ?」ツ?ッテ」ツ?ェテ」ツ??」ツ?凝」ツつ嘉」ツδォテ」ツδシテ」ツδ療」ツつ津ヲツ環愿」ツ?妥」ツつ?
                continue;
            }

            // テァツ崢ョテァツ堋?」ツ?ョテァツ環カテヲツ?凝」ツ?ォティツセツソテ」ツつ甘ァツ敖?」ツ??」ツ?淌」ツ?ェテ」ツつ嘉ヲツ篠「テァツエツ「テァツオツづ、ツコツ?
            if (ok(sv)){
                ans = sta.n;
                break;
            }

            // テ」ツ?敕」ツ??」ツ?ァテ」ツ?ェテ」ツ?妥」ツつ古」ツ?ーテッツシツ古、ツサツ甘」ツ?ョテァツ環カテヲツ?凝」ツ?凝」ツつ嘉ァツァツサテ」ツつ古」ツつ凝・ツ?ィテ」ツ?ヲテ」ツ?ョテァツ環カテヲツ?凝」ツつ智ueueテ」ツ?ォテ・ツ?・テ」ツつ古」ツつ?
            for (int i = 1; i < sv.size(); i++){
                // テ」ツつづ」ツ?療ゥツ堋」テ」ツ?ィテゥツ?陛」ツ??ィツ可イテ」ツ?ェテ」ツつ嘉ッツシツ?
                if (sv[i] != sv[i - 1]){
                    char a = sv[i];
                    char b = sv[i - 1];
                    sv[i] = sv[i - 1] = other(a, b);
                    q.push({ sv, sta.n + 1 });
                    sv[i] = a;
                    sv[i - 1] = b;
                }
            }
        }

        // ansテ」ツ?ョテ・ツ?、テ」ツ?古ヲツ崢エテヲツ鳴ーテ」ツ?陛」ツつ古」ツ?ヲテ」ツ??」ツ?ェテ」ツ?妥」ツつ古」ツ?ーテッツシツ古ァツュツ氾」ツ?暗」ツ?ィテ」ツ?ェテ」ツつ凝ヲツ可凝ゥツ??」ツ?ッティツヲツ凝」ツ?、テ」ツ?凝」ツ?」テ」ツ?ヲテ」ツ??」ツ?ェテ」ツ??
        if (ans == -1){
            cout << "NA" << endl;
        }
        else{
            cout << ans << endl;
        }
    }
}

// テ・ツ楪凝・ツ青催」ツ?ォautoテ」ツ?ィテヲツ崢クテ」ツ?湘」ツ?ィテ・ツ楪凝」ツつ津ヲツ篠ィティツォツ姪」ツ?療」ツ?ヲテ」ツ?湘」ツつ古」ツつ?C++11テゥツ卍静・ツョツ? g++ -std=c++11 a.cpp テ」ツ?ョテ」ツつ暗」ツ??」ツ?ォテ」ツつウテ」ツδウテ」ツδ妥」ツつ、テ」ツδォテ」ツ?凖」ツつ凝」ツ?ィテ、ツスツソテ」ツ?暗」ツつ凝ッツシツ?
// setテ」ツ?ョテ」ツδ。テ」ツδウテ」ツδ静」ツδシテゥツ鳴「テヲツ閉ーテ」ツ?景nsertテ」ツ?催」ツ?ョテヲツ按サテ」ツつ甘・ツ?、テ」ツ?ョテ・ツ楪凝」ツ?ッ pair<set<state>::const_iterator, bool> テ・ツ楪凝」ツ?ァテッツシツ古」ツ?禿」ツつ古」ツつ津ヲツ崢クテ」ツ?湘」ツ?ョテ」ツ?ッテ」ツ?療」ツつ禿」ツ?ゥテ」ツ??」ツ??
// autoテ」ツつ津、ツスツソテ」ツ?暗」ツ?ーテ」ツ?禿」ツ?ョテ」ツつ暗」ツ??」ツ?ェテゥツ閉キテ」ツ??・ツスツ「テ・ツ青催」ツつ津ァツ慊?ァツ閉・テ」ツ?ァテ」ツ?催」ツつ?テ・ツ楪凝ヲツ篠ィティツォツ?テッツシツ?
// auto pr = dp.insert(sv);
// テ」ツ?ッ
// pair<set<state>::const_iterator, bool> pr = dp.insert(sv);
// テ」ツ?ィテ・ツ青古」ツ?佚ッツシツ?