#include <iostream>
#include <set>
#include <string>
#include <queue>

using namespace std;

main(){
  string in;                    //¶ñÌúóÔ(ªÆÈé)
  while(cin>>in){
    if(in[0]=='0')break;        //I¹ð

    //gpÏÌú»
    int ans=-1;                 //answer(ðÉHèÂ¯È¢ê-1ÌÜÜ)
    set<string> vis;            //Tõµ½m[h
    queue<pair<string,int> > q; //ÉTõ·é¶ñðüêéB

    q.push(make_pair(in,0));    //ªðL[ÉüêéBÅZèÍà¿ëñ0
    vis.insert(in);             //¶ñssÍTõµ½B

    
    //TõÌæªcÁÄ¨èAðÉ½Çè¢ÄÈ¢ÀèTõ
    while(!q.empty()){
      //Tõm[hÌ¶ñÆA[³ðæèo·B
      string str=q.front().first;
      int depth=q.front().second;
      q.pop();
      
      //¶ñªê¶ÌÝ©ç\¬³êÄ¢é©ð»èB
      //ê¶ÌÝ©çÈÁÄ¢½êA¦ª©Â©Á½±ÆÉÈéÌÅTõðÅ¿ØéB
      int r=0,g=0,b=0;
      for(int i=0;i<str.size();i++){
        switch(str[i]){
        case 'r':++r;break;
        case 'g':++g;break;
        case 'b':++b;break;
        }
      }
      if(r==str.size() || g==str.size() || b==str.size()){
        ans=depth;
        break;
      }

      //ÙÈéñgÌ¶ðTµoµA»êðL[ÉlßéB
      for(int i=0;i<str.size()-1;i++){
        if(str[i]!=str[i+1]){
          string next(str);      //ðÁ¦é¶ñ(ÈºÌ3ÂÌif¶ÅKp)
          
          if( (str[i]=='b' && str[i+1]=='g') ||
              (str[i]=='g' && str[i+1]=='b')){
            next[i]='r';
            next[i+1]='r';
          }

          if( (str[i]=='r' && str[i+1]=='g') ||
              (str[i]=='g' && str[i+1]=='r')){
            next[i]='b';
            next[i+1]='b';
          }
          
          if( (str[i]=='b' && str[i+1]=='r') ||
              (str[i]=='r' && str[i+1]=='b')){
            next[i]='g';
            next[i+1]='g';
          }

          //·ÅÉTõµÄ¢½¶ñ¾Á½êXLbv
          if(vis.count(next)==1)continue;

          //Tõ\èÌm[hÆµÄL[ÉüêéB
          q.push(make_pair(next,depth+1));
          vis.insert(next);
        }
      }
    }
    
    if(ans==-1)cout<<"NA"<<endl;    //SÄðTõµÄàðª©Â©çÈ©Á½ê
    else cout<<ans<<endl;           //ðª©Â©Á½êÅZðoÍ
  }
}