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

typedef pair<string,int> bug;

bool check(string insect) {
  for ( int i = 1; i < insect.size(); i++ ) {
    if ( insect[0] != insect[i] ) return 0;
  }
  return 1;
}

char change( char a, char b ) {
  if ( a > b ) swap(a,b);
  if ( a == 'b' && b == 'g' ) return 'r';
  else if ( a == 'b' && b == 'r' ) return 'g';
  else return 'b';
}

void bfs ( string str ) {
  map<string,int> close;
  queue<bug> open;
  open.push(make_pair(str,0));
  close.insert(make_pair(str,1));
  int cnt = -1;
  while ( !open.empty() ) {
    bug b = open.front(); open.pop();
    string insect = b.first;
    if ( check(insect) ) {
      cnt = b.second;
      break;
    }
    
   
    for ( int i = 0; i < insect.size()-1; i++ ) {
      string tmp = insect;   
      if ( tmp[i] != tmp[i+1] ) {
	char nc = change( tmp[i],tmp[i+1] );
	tmp[i] = nc;
	tmp[i+1] = nc;
	if ( close[tmp] ) continue;
	open.push(make_pair(tmp,b.second+1));
	close[tmp] = 1;
      }
    }

  }
  
  if ( cnt == -1 ) cout << "NA" << endl;
  else cout << cnt << endl;
}

int main() {
  string str;
  while( cin >> str, str != "0" ) {
    bfs(str);
  }
  return 0;
}