#include<cstdio>
#include<queue>
#include<string>
#include<iostream>
#include<map>
#include<algorithm>
#include<set>
using namespace std;

int main(){
  string worm;
  cin>>worm;
  
  while(worm != "0"){
    queue<pair<string,int> >que;
    que.push(make_pair(worm,0));
    set<string> done_str;
    
    int ans = -1;
    
    while(!que.empty()){
      string s = que.front().first;
      int count = que.front().second;
      que.pop();

      string cmp_strR,cmp_strG,cmp_strB;

      cmp_strR.append(worm.size(), 'r');
      cmp_strG.append(worm.size(), 'g');
      cmp_strB.append(worm.size(), 'b');
      
      if(s == cmp_strR || s == cmp_strG || s == cmp_strB ){
	ans = count;
	break;
      }else if(done_str.find(s) != done_str.end()){
	continue;
      }else{
	done_str.insert(s);
      }

      for(int i=0;i<s.size()-1;i++){
	if(s.at(i) != s.at(i+1)){
	  if(s.at(i) != 'r' && s.at(i+1)!='r'){
	    string tmp = s;
	    que.push(make_pair(tmp.replace(i,2,2,'r'),count+1));

	  }else if(s.at(i) != 'g' && s.at(i+1)!='g'){
	    string tmp = s;
	    que.push(make_pair(tmp.replace(i,2,2,'g'),count+1));

	  }else if(s.at(i) != 'b' && s.at(i+1)!='b'){
	    string tmp = s;
	    que.push(make_pair(tmp.replace(i,2,2,'b'),count+1));
	  }
	}
      }
    }

    if(ans < 0){
      cout<<"NA"<<endl;
    }else{
      cout<<ans<<endl;
    }
    
    cin>>worm;
  }

  return 0;
}