#include<iostream>
#include<string>
#include<queue>
#include<map>
using namespace std;
int main(){

  string s,str,col[3];
  queue<string> que;
  map<string,int> mp;
  int flag;
  while(cin >> s,s != "0"){
    mp.clear();
    flag = 1;
    que.push(s);
    mp[s] = 0;
    for(int i=0;i<3;i++) col[i] = "";
    for(int i=0;i<s.size();i++){
      col[0] += "r";
      col[1] += "b";
      col[2] += "g";
    }
    while(!que.empty()){
      if(que.front()==col[0]){
	cout << mp[col[0]] << endl;
	flag--;
	break;
      }
      if(que.front()==col[1]){
	cout << mp[col[1]] << endl;
	flag--;
	break;
      }
      if(que.front()==col[2]){
	cout << mp[col[2]] << endl;
	flag--;
	break;
      }
      
      for(int i=0;i<s.size()-1;i++){
	str = que.front();
	if(str[i] != str[i+1]){
	  if(str[i] != 'r' && str[i+1] != 'r'){
	    str[i] = 'r';
	    str[i+1] = 'r';
	  } else if(str[i] != 'b' && str[i+1] != 'b'){
	    str[i] = 'b';
	    str[i+1] = 'b';
	  }else if(str[i] != 'g' && str[i+1] != 'g'){
	    str[i] = 'g';
	    str[i+1] = 'g';
	  }
	  if(mp.count(str) == 0){
	    que.push(str);
	    mp[str] = mp[que.front()]+1;
	  }
	}
      }
      que.pop();
    }
    while(!que.empty()) que.pop();
    if(flag) cout << "NA" << endl;
  }
  return (0);
}