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

using namespace std;

class sint{
	public:
	string st;int m;
	sint(){}
	sint(string a,int b){st=a;m=b;}
};

int musi(string str){
	queue<sint> state;
	map<string,int> mm;
	
	mm[str]=1;
	
	state.push(sint(str,0));
	
	while(1){
		
		if(state.empty()==1){
			break;
		}
		
		sint u;
		u=state.front();
		state.pop();
		
		
		
		//cout<<u.st<<" "<<u.m<<endl;
		
		int cont[3];
		cont[0]=cont[1]=cont[2]=0;
		for(int i=0;i<u.st.size();i++){
			if(u.st[i]=='r'){
				cont[0]++;
			}
			if(u.st[i]=='g'){
				cont[1]++;
			}
			if(u.st[i]=='b'){
				cont[2]++;
			}
		}
		int aaa=0;
		for(int i=0;i<3;i++){
			if(cont[i]==0){
				aaa++;
			}
		}
		if(aaa==2){
			return u.m;
		}
		
		for(int i=1;i<=u.st.size();i++){
			string nst=u.st;
			if(nst[i]!=nst[i-1]){
				if(nst[i]=='r'&&nst[i-1]=='g'){
					nst[i]=nst[i-1]='b';
				}
				if(nst[i]=='g'&&nst[i-1]=='b'){
					nst[i]=nst[i-1]='r';
				}
				if(nst[i]=='b'&&nst[i-1]=='r'){
					nst[i]=nst[i-1]='g';
				}
				if(nst[i-1]=='r'&&nst[i]=='g'){
					nst[i]=nst[i-1]='b';
				}
				if(nst[i-1]=='g'&&nst[i]=='b'){
					nst[i]=nst[i-1]='r';
				}
				if(nst[i-1]=='b'&&nst[i]=='r'){
					nst[i]=nst[i-1]='g';
				}
			}
			if(mm[nst]!=1){
				mm[nst]=1;
				state.push(sint(nst,u.m+1));
			}
			
		}
	}
	return -1;
}

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