#include<iostream>
#include<map>
#include<queue>
using namespace std;

string s;
char c[] = {'r','b','g'};

char rem(char a,char b){
  for(int i=0;i<3;i++){
    if(c[i] != a && c[i] != b)return c[i];
  }
  return 'x';
}

int main(){
  while(cin >> s,s!="0"){
    map<string,int> m;
    m[s] = 0;
    queue<string> q;
    q.push(s);
    
    int res = -1;
    while(q.size()){
      s = q.front(); q.pop();
      bool f = true;
      for(int i=0;i<s.size()-1;i++){
	if(s[i]!=s[i+1]){
	  f = false;
	  string tmp = s;
	  tmp[i] = tmp[i+1] = rem(s[i],s[i+1]);
	  if(m.find(tmp)==m.end()){
	    m[tmp] = m[s] + 1;
	    q.push(tmp);
	  }
	}
      }
      if(f){
	res = m[s];
	break;
      }
    }
    if(res<0)cout << "NA\n";
    else cout << res << endl;
  }
}	