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

#define	mp	make_pair

using namespace std;

typedef	pair<int,int>	pii;

bool isHomochrome(int stat,int len){
	int color=stat&3;
	for(int i=0;i<len;i++,stat>>=2)	if((stat&3)!=color)	return false;
	return true;
}

int getColor(int stat,int i){
	return (stat>>(2*i))&3;
}

void setColor(int &stat,int i,int c){
	stat&=~(3<<(2*i));
	stat|=c<<(2*i);
}

int main(){
	static int memo[1<<20];
	for(string worm;cin>>worm,worm!="0";){
		int len=worm.length();
		for(int i=0;i<(1<<(2*len));i++)	memo[i]=1<<30;

		int inistat=0;
		for(int i=0;i<len;i++){
			if(worm[i]=='r')	inistat=(inistat<<2)+0;
			if(worm[i]=='g')	inistat=(inistat<<2)+1;
			if(worm[i]=='b')	inistat=(inistat<<2)+2;
		}

		int ans=-1;
		memo[inistat]=0;
		queue<pii> qu;	qu.push(mp(0,inistat));
		while(!qu.empty()){
			pii a=qu.front();	qu.pop();
			int t=a.first,stat=a.second;
			if(isHomochrome(stat,len)){ ans=t; break; }
			for(int i=0;i<len-1;i++){
				int clr[]={getColor(stat,i),getColor(stat,i+1)};
				if(clr[0]!=clr[1]){
					int nextclr;
					for(int c=0;c<=2;c++)	if(clr[0]!=c && clr[1]!=c)	nextclr=c;
					int nextstat=stat;
					setColor(nextstat,i  ,nextclr);
					setColor(nextstat,i+1,nextclr);
					if(t+1<memo[nextstat]){
						qu.push(mp(t+1,nextstat));
						memo[nextstat]=t+1;
					}
				}
			}
		}

		if(~ans)	cout<<ans<<endl;
		else		cout<<"NA"<<endl;
	}

	return 0;
}