//01 = r, 10 = g, 11 = b

#include<iostream>
#include<queue>
#include<set>
#include<string>
#include<map>
#include<cmath>
using namespace std;

#define P pair<int, int>

int makeWormBit(string str);
void makeEnd(int size);
bool checkEnd(int n);
int changeColor(int n, int i, int size);
int searchChangeColor(int n, int i, int mask);
int makeResetMask(int size, int mask);

int endColor[3];

int main(){
    string str;
    while(cin >>str){
        if(str[0] == '0') break;
        int bw = makeWormBit(str), deep = 1;
        queue<P> q;
        set<int> s;
        q.push( make_pair(0, bw) );
        s.insert(bw);
        makeEnd(str.size());
        while(!q.empty()){
            P tmp = q.front();
            if(checkEnd(tmp.second)){
                cout <<tmp.first <<endl;
                break;
            } else{
                for(int i = 0; i < str.size() - 1; i++){
                    int t = changeColor(tmp.second, i, str.size());
                    if(s.find(t) == s.end()){
                        q.push( make_pair(tmp.first + 1, t) );
                        s.insert(t);
                    }
                }
            }
            q.pop();
        }
        if(q.empty()) cout <<"NA" <<endl;
    }
    return 0;
}

int makeWormBit(string str){
    int ret = 0;
    for(int i = 0; i < str.size(); i++){
        ret = ret << 2;
        if(str[i] == 'r') ret |= 1;
        else if(str[i] == 'g') ret |= 2;
        else if(str[i] == 'b') ret |= 3;
    }
    return ret;
}
bool checkEnd(int n){
    bool ret = false;
    for(int i = 0; i < 3; i++){
        if(endColor[i] == n){
            ret = true;
            break;
        }
    }
    return ret;
}
int changeColor(int n, int i, int size){
    int ret = n, mask = 15 << (i * 2), resetMask = makeResetMask(size, mask), color = searchChangeColor(n, i, mask);
    ret &= resetMask;
    ret |= (color << (i * 2));
    return ret;
}

void makeEnd(int size){
    int dx[] = {1, 2, 3}, ans;
    for(int i = 0; i < 3; i++){
        ans = 0;
        for(int j = 0; j < size; j++){
            ans = ans << 2;
            ans |= dx[i];
        }
        endColor[i] = ans;
    }
}

int searchChangeColor(int n, int i, int mask){
    int strc[] = {5, 10, 15, 6, 7, 9, 11, 13, 14}, strret[] = {5, 10, 15, 15, 10, 15, 5, 10, 5};
    int c = (n & mask), ret;
    c = c >> (i * 2);
    for(int i = 0; i < 9; i++){
        if(c == strc[i]) ret = strret[i];
    }
    return ret;
}

int makeResetMask(int size, int mask){
    int ret = 1 << (size * 2);
    ret--;
    ret ^= mask;
    return ret;
}