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

int bfs(string start);
bool isSameColor(string state);

int main(){
  string str;
  while(1){
    getline(cin,str);
    if(str=="0") break;

    int ans;
    ans=bfs(str);

    if(ans==-1) cout << "NA" << endl;
    else cout << ans << endl;
  }
  return 0;
}

bool isSameColor(string state){
  for(int i=1; i<state.size();i++){
    if(state[i-1]!=state[i]) return false;
  }
  return true;
}

int bfs(string start){
  queue<string> Q;
  map<string,int> data;
  map<string,bool> visited;
  string u, v;

  Q.push(start);
  data[start] = 0;
  visited[start] = true;

  while(!Q.empty()){
    u=Q.front(), Q.pop();
    if(isSameColor(u)) return data[u];
    for(int i=1;i<u.size();i++){
      if(u[i]!=u[i-1]){
	char firo;
        if(u[i]=='r'){
	  if(u[i-1]=='b') firo='g';
	  else if(u[i-1]=='g') firo='b';
	}
	else if(u[i]=='b'){
	  if(u[i-1]=='g') firo='r';
	  else if(u[i-1]=='r') firo='g';
	}
	else if(u[i]=='g'){
	  if(u[i-1]=='r') firo='b';
	  else if(u[i-1]=='b') firo='r';
	}

        v=u;
        v[i]=v[i-1]=firo;
        if(!visited[v]){
	  visited[v]=true;
	  data[v]=data[u]+1;
	  Q.push(v);
	}
      }
    }
  }
  return -1;
}