#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
struct Data{
    string s;
    int t;
    Data(string _s,int _t){
        s =_s,t =_t;
    }
};
map<string,bool> M;
int main(){
    string str;
    while(cin>>str,str!="0"){
        queue<Data> Q;
        Q.push(Data(str,0));
        while(!Q.empty()){
            Data E = Q.front();
            //cout<<E.s<<endl;
            Q.pop();
            if(M[E.s])continue;
            M[E.s] = true;
            bool flg = true;
            for(int i = 1;i < E.s.length();i++){
                if(E.s[i] != E.s[0])flg = false;
            }
            if(flg){
                cout<<E.t<<endl;
                goto e;
            }
            for(int i = 0;i < E.s.length()-1;i++){
                Data D = E;
                if(D.s[i]!=D.s[i+1]){
                    bool flg[3]={};
                    string w = "rgb";
                    if(D.s[i]=='r'||D.s[i+1]=='r')flg[0] = true;
                    if(D.s[i]=='g'||D.s[i+1]=='g')flg[1] = true;
                    if(D.s[i]=='b'||D.s[i+1]=='b')flg[2] = true;
                    for(int j = 0;j < 3;j++){
                        if(!flg[j])D.s[i] = D.s[i+1] = w[j];
                    }
                    D.t++;
                    //cout<<D.s<<endl;
                    Q.push(D);
                }
            }
        }
        cout<<"NA"<<endl;
        e:;
    }
}