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

typedef pair<string,int> bug;

bool check(string str ) {
  for ( int i = 1; i < str.size(); i++ ) {
    if ( str[0] != str[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 ) {
  int ans = -1;
  queue<bug> Q;
  map<string,int> close;

  Q.push( make_pair(str, 0) );
  close.insert( make_pair(str, 1) );

  while( !Q.empty() ) {
    bug b = Q.front(); Q.pop();
    string tmp1 = b.first;
    if ( check(tmp1) ) {
      ans = b.second;
      break;
    }

    for ( int i = 0; i < tmp1.size()-1; i++ ) {
      if ( tmp1[i] != tmp1[i+1] ) {
	string tmp2 = tmp1;
	char nc = change(tmp2[i],tmp2[i+1]);
	tmp2[i] = nc;
	tmp2[i+1] = nc;
	if ( close[tmp2] ) continue;
	Q.push( make_pair(tmp2,b.second+1) );
	close[tmp2] = 1;
	
      }
    }

  }

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

}


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

  return 0;
}