//57
#include<iostream>
#include<vector>
#include<set>
#include<queue>
#include<utility>

using namespace std;

int main(){
  for(char w[11];cin>>w,w[0]!='0';){
    queue<pair<vector<int>,int> >que;
    vector<int> in;
    for(int i=0;w[i];i++){
      int n=(w[i]=='r')?1:(w[i]=='g')?2:4;
      in.push_back(n);
    }
    que.push(make_pair(in,0));
    set<vector<int> > s;
    while(!que.empty()){
      vector<int> v=que.front().first;
      if(s.find(v)!=s.end()){
	que.pop();
      }else{
	s.insert(v);
	int c=0;
	for(int i=0;i<v.size();i++){
	  c|=v[i];
	}
	if((c&(c-1))==0)break;
	for(int i=0;i<v.size()-1;i++){
	  if(v[i]!=v[i+1]){
	    vector<int> n=v;
	    int nc=7^v[i]^v[i+1];
	    n[i]=n[i+1]=nc;
	    que.push(make_pair(n,que.front().second+1));
	  }
	}
	que.pop();
      }
    }
    if(que.empty()){
      cout<<"NA"<<endl;
    }else{
      cout<<que.front().second<<endl;
    }
  }
  return 0;
}