#include <iostream>
#include <vector>
#include <map>
#include <climits>
#include <queue>
using namespace std;

map<int,bool> isre;
map<int,int> dp;

int code(string s){
    int ret=0,kake=1;
    for(int i=0;i<s.size();i++){
        if(s[i]=='r') ret+=kake*1;
        else if(s[i]=='g') ret+=kake*2;
        else ret+=kake*3;
        kake*=4;
    }
    return ret;
}

int main(){
    string in;
    for(;;){
        cin>>in;
        if(in=="0") break;
        map<int,bool> isre;
        queue<string> nq;
        nq.push(in);
        int ret=-1;
        int cnt=0;
        while(!nq.empty()){
            int sz=nq.size();
            for(int i=0;i<sz;i++){
                string now=nq.front();
                nq.pop();
                int co=code(now);
                if(isre.find(co)!=isre.end() && isre[co]) continue;
                isre[co]=true;
                bool is=true;
                for(int j=0;j<now.size();j++){
                    if(now[j]!=now[0]) is=false;
                }
                if(is){
                    ret=cnt;
                    goto EXIT;
                }
                for(int j=1;j<now.size();j++){
                    string ne=now;
                    if(now[j-1]!=now[j]){
                        if(now[j-1]!='r'&&now[j]!='r'){
                            ne[j-1]=ne[j]='r';
                        }else if(now[j-1]!='g'&&now[j]!='g'){
                            ne[j-1]=ne[j]='g';
                        }else{
                            ne[j-1]=ne[j]='b';
                        }
                        nq.push(ne);
                    }
                }
            }
            cnt++;
        }
EXIT:   ;
        if(ret==-1) cout<<"NA"<<endl;
        else cout<<ret<<endl;
    }
}