#include <iostream>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
#define pp(a,b) push(make_pair(a,b))
typedef pair<string,int> NODE;
char color(char a, char b){
	if(a>b)swap(a,b);
	if(a==b)return a;
	if(a=='b' && b=='r')return 'g';
	if(a=='b' && b=='g')return 'r';
	if(a=='g' && b=='r')return 'b';
	cout << "unko" << endl;
}
int main(){
	string n;
	char p1,p2;
	map<string,bool> done;
	while(cin >> n && n != "0"){
		bool f = false;
		queue<NODE> Q;
		done.clear();
		Q.pp(n,0);
		while(Q.size()){
			NODE q = Q.front();
			Q.pop();
			if( count(q.first.begin(),q.first.end(),'r') == q.first.size() || 
			    count(q.first.begin(),q.first.end(),'g') == q.first.size() ||
			    count(q.first.begin(),q.first.end(),'b') == q.first.size()
			){
				cout << q.second << endl;
				f = true;
				break;
			} 
			for(int i=0;i+1<q.first.size();i++){
				p1 = q.first[i];p2 = q.first[i+1];
				q.first[i] = q.first[i+1] = color(p1,p2);
				if(!done[q.first]){
					Q.pp(q.first,q.second+1);
					done[q.first] = true;
				}
				q.first[i] = p1;
				q.first[i+1] = p2;
			}
		}
		if(!f)cout << "NA" << endl;
	}
}