#include <iostream>
#include <utility>
#include <vector>
#include <set>
#include <queue>
using namespace std;

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


char othercolor(char a, char b){
  if(a != b){
    if(a != 'r' && b != 'r'){ return 'r'; }
    if(a != 'g' && b != 'g'){ return 'g'; }
    if(a != 'b' && b != 'b'){ return 'b'; }
  }
  return -1;
}


int main(void){
  while(true){
    string initworm;
    cin >> initworm;
    if(initworm == "0"){ break; }

    queue<pair<int, string> > wait;
    set<string> used;
    wait.push(make_pair(0, initworm));
    used.insert(initworm);
    
    int ans = -1;
    while(!wait.empty()){
      int nowcost = wait.front().first;
      string nowworm = wait.front().second;
      wait.pop();

      if(terminal(nowworm)){
        ans = nowcost;
        break;
      }

      // ??£??\??¶???
      for(int i = 1; i < (int)nowworm.size(); i++){
        char c = othercolor(nowworm[i], nowworm[i - 1]);
        // ???????????????????????????????????§???????????????
        if(c != -1){
          string next = nowworm;
          next[i] = next[i - 1] = c;
          // ????????¶???????????¢?´¢?????£?????´???
          if(used.count(next) == 0){
            used.insert(next);
            wait.push(make_pair(nowcost + 1, next));
          } 
        }
      }      
    }
    
    // ??????
    if(ans == -1){ cout << "NA" << endl; }
    else{ cout << ans << endl; }
  }
  return 0;
}