#include <iostream>
#include <set>
#include <map>
#include <queue>
#include <algorithm>

using namespace std;

int change( string target )
{
	int a = 1;
	int sum = 0;

	for( int i = 0;i < target.size();i++ ){
		if( target[i] == 'r' ) target[i] = 0;
		else if( target[i] == 'g' ) target[i] = 1;
		else if( target[i] == 'b' ) target[i] = 2;
		
		sum += target[i] * a;
		a *= 3;
	}

	return sum;
}

		

int bfs( string target )
{
	set<int> history;
	queue<string> data;
	map<string,int> dist;

	data.push( target );
	dist[target] = 0;

	while( !data.empty() ){
		const string u = data.front();
		if( count( u.begin(), u.end(), 'r' ) == u.size() || count( u.begin(), u.end(), 'g' ) == u.size() || count( u.begin(), u.end(), 'b' ) == u.size() ) return dist[u];

		for( int i = 0;i < u.size() - 1;i++ ){
			if( u[i] != u[i + 1] ){
				string hoge = u;
				hoge[i] = hoge[i + 1] = ( 'r' + 'g' + 'b' ) - ( hoge[i] + hoge[i + 1] );
				int piyo = change( hoge );
				if( history.count( piyo ) ) continue;
				history.insert( piyo );
				data.push( hoge );
				dist[hoge] = dist[u] + 1;
			}
		}

		data.pop();
	}
	return -1;

}

int main(int argc, char const* argv[])
{
	string target;

	while( cin >> target && target != "0" ){
		int answer = bfs( target );
		if( answer != -1 ) cout << answer << endl;
		else cout << "NA" << endl;
	}
}