#include<bits/stdc++.h>
using namespace std;
char c[3]={'r','g','b'};
main(){
  string w;
  while(cin>>w,w[0]!='0'){
    unordered_set<string>a;
    a.insert(w);
    queue<pair<string,int> >q;
    q.push(make_pair(w,0));
    while(!q.empty()){
      pair<string,int>ww=q.front();q.pop();
      string s=ww.first;//cout<<s<<endl;
      int d=ww.second;//cout<<d<<endl;
      int cc=0;
      for(int i=0;i<s.size()-1;i++)if(s[i]!=s[i+1])cc++;
      if(!cc){cout<<d<<endl;goto L;}
      for(int i=0;i<s.size()-1;i++){
        if(s[i]!=s[i+1]){
          int p=0;
          for(int k=0;k<3;k++)
            for(int j=0;j<3;j++)
              if(s[i]==c[k]&&s[i+1]==c[j])p=k+j;
          string t=s;
          if(p==3)t[i+1]=t[i]='r';
          else if(p==2)t[i+1]=t[i]='g';
          else t[i+1]=t[i]='b';
          if(!a.count(t)){//cout<<t<<endl;
            q.push(make_pair(t,d+1));
            a.insert(t);
          }
        }
      }
    }
    cout<<"NA"<<endl;
    L:;
  }
}