#include <cstdio>
#include <utility>
#include <string>
#include <queue>
#include <set>

using namespace std;

static int
validate (
  const char * s
  )
{
  while ( *( ++s ) != '\0' )
  {
    if ( s[ -1 ] != s[ 0 ] )  return ( 0 );
  }

  return ( 1 );
}

/** Application main entry point. */
int
main (
  int     argc,
  char  * argv[ ]
  )
{
  int i;

  for ( ; ; )
  {
    typedef pair<string,int> Point;
    queue<Point> lis;
    set<string> h;
    char si[ 11 ];

    scanf ( " %s", si );
    if ( *si == '0' ) break ;

    lis.push ( make_pair ( si, 0 ) );
    h.insert ( si );
    while ( !lis.empty ( ) )
    {
      const Point s = lis.front ( );
      lis.pop ( );

      if ( validate ( s.first.c_str ( ) ) )
      {
        printf ( "%d\n", s.second );
        goto ESC;
      }

      for ( i = 1; i < s.first.size ( ); ++i )
      {
        if ( s.first[ i - 1 ] != s.first[ i ] )
        {
          string g = s.first;

          if ( ( g[ i - 1 ] == 'r' && g[ i ] == 'g' )
            || ( g[ i - 1 ] == 'g' && g[ i ] == 'r' ) )
          {
            g.replace ( i - 1, 2, "bb" );
          }
          if ( ( g[ i - 1 ] == 'g' && g[ i ] == 'b' )
            || ( g[ i - 1 ] == 'b' && g[ i ] == 'g' ) )
          {
            g.replace ( i - 1, 2, "rr" );
          }
          if ( ( g[ i - 1 ] == 'b' && g[ i ] == 'r' )
            || ( g[ i - 1 ] == 'r' && g[ i ] == 'b' ) )
          {
            g.replace ( i - 1, 2, "gg" );
          }

          if ( h.find ( g ) == h.end ( ) )
          {
            lis.push ( make_pair ( g, s.second + 1 ) );
            h.insert ( g );
          }
        }
      }
    }
    puts ( "NA" );

ESC: ;
  }

  return ( 0 );
}