#include<bits/stdc++.h>
using namespace std;
queue <pair<string,int> > worm;
map <string,int> M;
int s1,n;
string str,strrr,sample[3]={"gggggggggg","bbbbbbbbbb","rrrrrrrrrr"},worms[3];
bool flag=false;

int main(){
    while(1){
        cin >> str;
        if(str=="0")break;
            s1=str.size();
            for(int i=0;i<3;i++)worms[i]=sample[i].substr(0,s1);
            worm.push(make_pair(str,0));


        while(!worm.empty()){
            str=worm.front().first;
            n=worm.front().second;
            worm.pop();
            //cout << n << endl;
            if(s1<n)break;
            if(str==worms[0]||str==worms[1]||str==worms[2]){
                    flag=true;
                cout  << n << endl;
                while(!worm.empty())worm.pop();
                break;
            }else{
                for(int i=1;i<s1;i++){
                    if(str[i]!=str[i-1]){
                        if(str[i]!='r'&&str[i-1]!='r'){
                            strrr=str;
                            str[i]='r',str[i-1]='r';
                            worm.push(make_pair(str,n+1));
                            str=strrr;
                        }
                        if(str[i]!='b'&&str[i-1]!='b'){
                            strrr=str;
                            str[i]='b',str[i-1]='b';
                            worm.push(make_pair(str,n+1));
                            str=strrr;
                        }
                        if(str[i]!='g'&&str[i-1]!='g'){
                            strrr=str;
                            str[i]='g',str[i-1]='g';
                            worm.push(make_pair(str,n+1));
                            str=strrr;
                        }
                    }
                }

            }


    //end:
    }

        if(flag==false)cout << "NA" << endl;
        flag=false;
        while(!worm.empty())worm.pop();
        n=0;

    }

return 0;
}