#include <iostream>
#include <string>
#include <set>
#include <vector>
#include <queue>
using namespace std;

int main()
{
	string s;
	char c[] = { "rgb" };

	while( cin >> s && s != "0" ){
		set< string > memo;
		vector< string > sample;
		for( int i = 0; i < 3; ++i ){
			sample.push_back( string( s.size(), c[ i ] ) );
		}

		queue< string > pattern;
		pattern.push( s );
		int sec = 0;
		bool found = false;
		while( !pattern.empty() ){
			int size = pattern.size();
			while( size > 0 ){
				string p = pattern.front();
				pattern.pop();
				if( memo.find( p ) != memo.end() ){
					--size;
					continue;
				}
				memo.insert( p );
				for( int i = 0; i < 3; ++i ){
					if( p == sample[ i ] ){
						found = true;
						break;
					}
				}
				if( found ) break;

				for( int i = 0; i < (int)p.size() - 1; ++i ){
					if( p[ i ] == p[ i + 1 ] ){
						continue;
					}
					int oo = p[ i ] + p[ i + 1 ];
					char color;
					switch( oo ){
						case 'r' + 'g': color = 'b'; break;
						case 'g' + 'b': color = 'r'; break;
						case 'b' + 'r': color = 'g'; break;
					}
					string cpy = p;
					cpy[ i ] = cpy[ i + 1 ] = color;
					pattern.push( cpy );
				}
				--size;
			}
			if( found ) break;
			++sec;
		}
		if( found ){
			cout << sec << endl;
		}else{
			cout << "NA" << endl;
		}
	}

	return 0;
}