#include <iostream>
#include <string>
#include <queue>
#include <utility>
#include <set>
using namespace std;
typedef pair<string,int> P;
int main() {
    string S;
    while(cin>>S,S[0]!='0') {
        set<string> ST;
        queue<P> Q;
        Q.push(P(S,0));
        string R,G,B;
        bool OK;
        while(!Q.empty()) {
            P p=Q.front();Q.pop();
            OK=true;
            for(int i=0;i<p.first.size()-1;i++) {
                string SS=p.first;
                if((p.first[i]=='r'&&p.first[i+1]=='g')||(p.first[i]=='g'&&p.first[i+1]=='r')) {
                        SS[i]=SS[i+1]='b';
                        if(ST.find(SS)==ST.end()){
                            Q.push(P(SS,p.second+1));
                            ST.insert(SS);
                        }
                        OK=false;
                }else if((p.first[i]=='r'&&p.first[i+1]=='b')||(p.first[i]=='b'&&p.first[i+1]=='r')) {
                        SS[i]=SS[i+1]='g';
                        if(ST.find(SS)==ST.end()){
                            Q.push(P(SS,p.second+1));
                            ST.insert(SS);
                        }
                        OK=false;
                }else if((p.first[i]=='g'&&p.first[i+1]=='b')||(p.first[i]=='b'&&p.first[i+1]=='g')) {
                        SS[i]=SS[i+1]='r';
                        if(ST.find(SS)==ST.end()){
                            Q.push(P(SS,p.second+1));
                            ST.insert(SS);
                        }
                        OK=false;
                }
            }
            if(OK) {cout<<p.second<<endl;break;}
        }
        if(!OK)cout<<"NA"<<endl;
    }
}