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

int main(){
  int i,j,k,n;
  string str,ans,a1,a2,a3;
  while(1){
    cin >> str;
    if(str == "0") break;
    queue <string> Q;
    map <string,int> d,f;

    a1 = "r";
    a2 = "b";
    a3 = "g";
    for(i=1;i<str.size();i++){
    a1 += "r";
    a2 += "b";
    a3 += "g";
  }

    d[str] = 0;
    Q.push(str);
    ans = "NA";

    while(!Q.empty()){
      string u,v;
      u = Q.front();
      Q.pop();
      f[u] = 1;
      if(u == a1 || u == a2 || u == a3){
	ans = u;
	break;
      }

      for(i=0;i<u.size()-1;i++){
	if(u[i] == 'r' && u[i+1] == 'g' || u[i] == 'g' && u[i+1] == 'r'){
	  v = u;
	  v[i] = v[i+1] = 'b';
	  
	  if(!f[v]){
	    d[v] = d[u] + 1;
	    Q.push(v);
	    f[v] = 1;
	  }
	}

	else if(u[i] == 'r' && u[i+1] == 'b' || u[i] == 'b' && u[i+1] == 'r'){
	  v = u;
	  v[i] = v[i+1] = 'g';

	  if(!f[v]){
	    d[v] = d[u] + 1;
	    Q.push(v);
	    f[v] = 1;
	  }
	}
	
	else if(u[i] == 'g' && u[i+1] == 'b' || u[i] == 'b' && u[i+1] == 'g'){
	  v = u;
	  v[i] = v[i+1] = 'r';
	  
	  if(!f[v]){
	    d[v] = d[u] + 1;
	    Q.push(v);
	    f[v] = 1;
	  }
	}
      }
    }
    if(ans != "NA") cout << d[ans] << endl;
    else cout << "NA" << endl;
  }
  return 0;
}