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

bool is_goal( string s )
{
	bool ok = true;
	for ( int i = 0; i + 1 < s.size(); i++ ) if ( s[i] != s[i+1] ) ok = false;
	return ok;
}

char change_color( char a, char b )
{
	if ( a == 'r' )
		return ( b == 'g' ) ? 'b' : 'g';

	else if ( a == 'g' )
		return ( b == 'b' ) ? 'r' : 'b';

	else if ( a == 'b' )
		return ( b == 'r' ) ? 'g' : 'r';

	return ' ';
}

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

		map <string, int>	V;
		queue <string>		Q;

		V[in] = 0;
		Q.push( in );

		int kotae = -1;
		while ( Q.empty() == false )
		{
			string now = Q.front();
			Q.pop();

			if ( is_goal( now ) )
			{
				kotae = V[now];
				break;
			}

			for ( int i = 0; i + 1 < now.size(); i++ )
			{
				string tmp = now;
				if ( tmp[i] != tmp[i+1] )
				{
					tmp[i] = tmp[i+1] = change_color( tmp[i], tmp[i+1] );
				}

				if ( V.find( tmp ) == V.end() )
				{
					V[tmp] = V[now] + 1;
					Q.push( tmp );
				}

			}

		}

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

	}
	return 0;
}