#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <iterator>
#include <map>
#include <set>
using namespace std;
typedef pair<vector<char>, int> VCI;
bool check(vector<char> worm){
  for(int i = 1; i < worm.size(); ++i){
    if(worm[0] != worm[i]){
      return false;
    }
  }
  return true;
}
map<pair<char, char>, char> table;
int bfs(string s){
  vector<char> worm;
  copy(s.begin(), s.end(), back_inserter(worm));
  int N = worm.size();
  queue<VCI> q;
  set<vector<char> > visited;
  q.push(make_pair(worm, 0));
  while(!q.empty()){
    VCI vci = q.front(); q.pop();
    vector<char> w = vci.first;
    int step = vci.second;
    if(check(w)){
      return step;
    }
    if(visited.find(w) != visited.end()){
      continue;
    }
    visited.insert(w);
    for(int i = 0; i < N-1; ++i){
      if(w[i] == w[i+1]){
        continue;
      }
      vector<char> nw;
      copy(w.begin(), w.end(), back_inserter(nw));
      nw[i] = nw[i+1] = table[make_pair(nw[i], nw[i+1])];
      q.push(make_pair(nw, step+1));
    }
  }
  return -1;
}

int main(){
  table[make_pair('r', 'b')] = table[make_pair('b', 'r')] = 'g';
  table[make_pair('r', 'g')] = table[make_pair('g', 'r')] = 'b';
  table[make_pair('b', 'g')] = table[make_pair('g', 'b')] = 'r';
  string s;
  while(true){
    cin >> s;
    if(s == "0"){
      break;
    }
    int ans = bfs(s);
    if(ans == -1){
      cout << "NA" << endl;
    }
    else{
      cout << bfs(s) << endl;
    }
  }
  return 0;
}