#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
char p[3][12]={
    "rrrrrrrrrr",
    "bbbbbbbbbb",
    "gggggggggg"
};
typedef struct worm{
    char b[12];
    int s;
}worm;
using namespace std;
int main(){
    char a[15];
    while(cin>>a,a[0]!='0'){
        int len=strlen(a);
        queue<worm>Q;
        worm o;
        strcpy(o.b,a);
        o.s=0;
        Q.push(o);
        bool f=true;
        while(Q.size()){
            worm gar=Q.front();
            Q.pop();
            bool f2=false;
            for(int i=0;i<3;i++)if(!strncmp(gar.b,p[i],len))f2=true;
            if(f2){
                cout<<gar.s<<endl;
                f=false;
                break;
            }
            if(gar.s>9)break;
            for(int i=0;i<len-1;i++){
                char gar2[12];
                strcpy(gar2,gar.b);

                if(gar2[i]!=gar2[i+1]){
                    if(gar2[i]!='g'&&gar2[i+1]!='g')strncpy(gar2+i,p[2],2);
                    else if(gar2[i]!='r'&&gar2[i+1]!='r')strncpy(gar2+i,p[0],2);
                    else if(gar2[i]!='b'&&gar2[i+1]!='b')strncpy(gar2+i,p[1],2);
                }
                if(strcmp(gar.b,gar2)){
                    worm gar3;
                    strcpy(gar3.b,gar2);
                    gar3.s=gar.s+1;
                    Q.push(gar3);
                }
            }

        }
        if(f)cout<<"NA"<<endl;
    }

    return 0;
}