#include<iostream>
#include<queue>
#include<map>
#include<string>
using namespace std;
typedef pair<string,int> P;
int bfs(string);
int main(){
    string worm;
    while(cin>>worm,worm!="0"){
        int rep=bfs(worm);
        if(rep>=0)cout<<rep<<endl;
        else cout<<"NA"<<endl;
    }
    return 0;
}

int bfs(string worm){
    queue<P>Q;
    map<string,bool>M;
    Q.push(make_pair(worm,0));

    while(Q.size()){
        P p=Q.front();
        Q.pop();
        if(M[p.first])continue;
        M[p.first]=true;
        string str=p.first;
        bool flag=false;
        for(int i=0;i<str.size()-1;i++)
            if(str[i]!=str[i+1])flag=true;

        if(!flag)return p.second;

        for(int i=0;i<str.size()-1;i++){
            string next=str;
            char temp;
            if(next[i]!=next[i+1]){
                if(next[i]!='g'&&next[i+1]!='g')temp='g';
                else if(next[i]!='r'&&next[i+1]!='r')temp='r';
                else temp='b';

                next[i]=next[i+1]=temp;
                Q.push(make_pair(next,p.second+1));
            }
        }


        }

        return -1;



}