#include<iostream>
#include<algorithm>
#include<string>
#include<map>
using namespace std;
map<string, int> cache;
bool same(string seq){
  for(int i = 0; seq[i+1] != '\0'; ++i){
    if(seq[i] != seq[i+1]){
      return false;
    }
  }
  return true;
}
int dls(string seq, int depth){
  if(depth<0){
    return false;
  }
  if(same(seq)){
    return true;
  }
  if(cache.find(seq) != cache.end() && cache[seq] >= depth){
    return false;
  }
  else{
    cache[seq] = depth;
  }
  for(int i = 0; seq[i+1] != '\0'; ++i){
    char t = seq[i];
    char n = seq[i+1];
    if(t != n){
      if((t + n) == ('r' + 'b')){
        seq[i] = seq[i+1] = 'g';
      }
      else if((t + n) == ('r' + 'g')){
        seq[i] = seq[i+1] = 'b';
      }
      else{
        seq[i] = seq[i+1] = 'r';
      }
      if(dls(seq, depth-1)){
        return true;
      }
      seq[i] = t;
      seq[i+1] = n;
    }
  }
  return false;
}
void iddfs(string seq){
  cache = map<string, int>();
  for(int depth = 0;depth <= 20; ++depth){
    if(dls(seq, depth)){
      cout << depth << endl;
      return;
    }
  }
  cout << "NA" << endl;
}
int main(){
  char seq[11];
  while(true){
    cin >> seq;
    if(seq[0] == '0'){
      break;
    }
    iddfs(seq);
  }
  return 0;
}