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

map<string, int> seenbefore;
string in;
map<string, int>::iterator it;

string check(string twochars){
  if(twochars[0] == twochars[1]) return "";
  if(twochars[0] == 'r')
    if(twochars[1] == 'g') return "b";
    else return "g";
  else
    if(twochars[0] == 'g')
      if(twochars[1] == 'r') return "b";
      else return "r";
    else
      if(twochars[1] == 'r') return "g";
      else return "r";
}

int next_generation(string now, int gen){
  if(now.find("r") + now.find("g") + now.find("b") == -2) return gen;
  if((it = seenbefore.find(now)) != seenbefore.end()){
    if((*it).second > gen) (*it).second = gen;
    else return -1;
  }
  seenbefore.insert(map<string, int>::value_type(now, gen));
  int len = now.length();
  int ans = 99999999, y;
  for(int i = 0; i < len - 1; i++){
    string che = check(now.substr(i, 2));
    if(che != ""){
      y = next_generation(now.substr(0, i) + che + che + now.substr(i+2), gen + 1);
      if(y != -1) ans = min(ans, y);
    }
  }
  return ans;
}

int main(){
  while((cin >> in), in != "0"){
    seenbefore.clear();
    int x = next_generation(in, 0);
    if (x >= 0) cout << x << endl;
    else cout << "NA" << endl;
  }
  return 0;
}