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

int f(char a,char b){
	if( a == 'r' && b == 'g' ) return 'b';
	if( a == 'b' && b == 'r' ) return 'g';
	if( a == 'b' && b == 'g' ) return 'r';
	swap(a,b);
	if( a == 'r' && b == 'g' ) return 'b';
	if( a == 'b' && b == 'r' ) return 'g';
	if( a == 'b' && b == 'g' ) return 'r';
	return 0;
}

int main(){
	string s;
	while(cin >> s && s != "0" ){
		map<string,int> done;
		queue< pair<string,int> > Q;
		Q.push(make_pair(s,0));
		while(Q.size()){
			pair<string,int> q = Q.front(); Q.pop();
			if( done[q.first]++) continue;
			if( count(q.first.begin(),q.first.end(),q.first[0]) == q.first.size() ) {
				cout << q.second << endl;
				goto exit;
			}
			for(int i = 0 ; i < q.first.size() - 1 ; i++){
				if( f(q.first[i],q.first[i+1]) ){
					char c = f(q.first[i],q.first[i+1]);
					string next = q.first;
					next[i] = next[i+1] = c;
					Q.push(make_pair(next,q.second+1));
				}
			}
		}
		cout << "NA" << endl;
		exit:;
	}
}