#include <iostream>
#include <queue>
#include <map>
#define INF 10000000
using namespace std;
typedef pair<string ,int>P;
int cnt;

int bfs(string worm){
  queue<P> que;
  que.push(P(worm,cnt));
  string next;
  char tmp;
  while(!que.empty()){
    P p = que.front();
    que.pop();
    bool f = true;
    for(int i = 0 ; i < p.first.size()-1 ; i++ ){
      if(worm[i] != worm[i+1])f = false;
    }
    if(f)return p.second;
  for(int i = 0 ; i < worm.size()-1 ; i++ ){
    if(worm[i] != worm[i+1]){
      if(worm[i] != 'r' && worm[i+1] != 'r'){
	tmp = 'r';
      }else if(worm[i] != 'g' && worm[i+1] != 'g'){
	tmp = 'g';
      } else {
	tmp = 'b';
      }
      next = worm;
      next[i] = next[i+1] = tmp;
      que.push(P(next,cnt+1));
    }
  }
  }
  return -1;
}

int main(){
  string worm;
  while(cin >> worm){
    if(worm[0] == '0')break;
    cnt = 0;
    int ret = bfs(worm);
    if(ret == -1){
      cout << "NA" << endl;
    }else cout << ret << endl;

  }
  return 0;
}