#include<iostream>
#include<string>
#include<map>
#include<queue>

#define rep(i,n) for(int i=0;i<int(n);i++)

using namespace std;


class Q{
	public:
	string str;
	int dep;
	//Q(string a,int n){str=a;dep=n;}
	Q(string str, int dep) : str(str), dep(dep) {}
};

int saiki(string imo){
	
	queue<Q> que;
	
	que.push(Q(imo,0));
	
	map<string,int> visit;
	
	while(1){
		
		if(que.empty()==1){
			return -1;
		}
		
		Q u = que.front();
		que.pop();
		
		string s = u.str;
		
		if(visit[s]==1){
			continue;
		}
		visit[s]=1;
		
		
		//printf("%d pop( %s )\n",u.dep,s.c_str());
		char ch=s[0];
		int flg=1;
		rep(i,s.size()-1){
			if(s[i+1]!=ch) {flg=0;break;}
		}
		if(flg==1){
			return u.dep;
		}
		
		rep(i,s.size()-1){
			
			if((s[i]=='r' && s[i+1]=='g')||(s[i+1]=='r' && s[i]=='g')){
				string t=s;
				t[i]=t[i+1]='b';
				que.push(Q(t,u.dep+1));
		//printf("%d push( %s )\n",u.dep,t.c_str());
			}else
			if((s[i]=='b' && s[i+1]=='r')||(s[i+1]=='b' && s[i]=='r')){
				string t=s;
				t[i]=t[i+1]='g';
				que.push(Q(t,u.dep+1));
		//printf("%d push( %s )\n",u.dep,t.c_str());
			}else
			if((s[i]=='g' && s[i+1]=='b')||(s[i+1]=='g' && s[i]=='b')){
				string t=s;
				t[i]=t[i+1]='r';
				que.push(Q(t,u.dep+1));
		//printf("%d push( %s )\n",u.dep,t.c_str());
			}
		}
	}
	return 100;
	
}

int main(){
	while(1){
		string a;
		cin>>a;
		
		if(a=="0"){
			break;
		}
		
		int ans=saiki(a);
		
		if(ans==-1){
			puts("NA");
		}else{
		printf("%d\n",ans);
		}
	}
}