#include<iostream>
#include<string>
#include<set>
#include<queue>
using namespace std;
char conv(char c1,char c2){
  if(c1=='r'){
    if(c2=='g')return 'b';
    if(c2=='b')return 'g';
  }else if(c1=='g'){
    if(c2=='r')return 'b';
    if(c2=='b')return 'r';
  }else if(c1=='b'){
    if(c2=='r')return 'g';
    if(c2=='g')return 'r';
  }
}
int bfs(string s){
  queue< pair<int, string> > qs;
  set<string> vis;
  qs.push( make_pair(0,s) );
  while(!qs.empty()){
    bool bFound=false;
    int ret = qs.front().first;
    string now = qs.front().second;
    qs.pop();

    //cout << vis.size() << endl;
    if( vis.find(now) != vis.end() ){
      continue;
    }
    vis.insert(now);
    for(int i = 0; i < now.length()-1; ++i){
      if(now[i]!=now[i+1]){
	bFound = true;
	string next = now;
	char nc = conv(now[i],now[i+1]);
	next[i] = next[i+1] = nc;
	qs.push(make_pair(ret+1,next));
      }
    }
    if(!bFound){
      //cout << now << endl;
      return ret;
    }
  }
  return -1;
}
int main(){
  while(true){
    string s;
    cin >> s;
    if( s == "0" )  break;
    int ans = bfs(s);
    if( ans < 0 )
      cout << "NA" << endl;
    else
      cout << ans << endl;    
  }
  return 0;
}