#include<bits/stdc++.h>
using namespace std;

int main(){
  typedef pair<string,int>P;
  while(1){
    string str;
    map<string,int>maps;
    queue<P>que;
    int kaku=0;
    cin>>str;
    if(str[0]=='0')break;
     que.push(P(str,0));
     while(!que.empty()){
       P p=que.front();que.pop();
       string  now,turn;
       int cnt=1;
       int ans;
       now=p.first;
       turn=p.first;
       ans=p.second;
       //   cout<<now<<" "<<ans<<endl;
       if(maps[now]==1)continue;
       maps[now]=1;
       
       for(int i=0;i<str.size()-1;i++){
	 if(now[i]==now[i+1])cnt++;
       }
       if(cnt==str.size()){
	 cout<<ans<<endl;
	 kaku=1;
	 break;
       }
       for(int i=0;i<str.size()-1;i++){
	 if(now[i]=='b' && now[i+1]=='r' || now[i]=='r' && now[i+1]=='b'){
	   now[i]='g';now[i+1]='g';
	   que.push(P(now,ans+1));
	   now=turn;
	 }
	 if(now[i]=='r' && now[i+1]=='g' || now[i]=='g' && now[i+1]=='r'){
	   now[i]='b';now[i+1]='b';
	   que.push(P(now,ans+1));
	   now=turn;
	 }
	 if(now[i]=='b' && now[i+1]=='g' || now[i]=='g' && now[i+1]=='b'){
	   now[i]='r';now[i+1]='r';
	   que.push(P(now,ans+1));
	   now=turn;
	 }
       }
     }
     if(!kaku)cout<<"NA"<<endl;
  }   
}