#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int que[60000][10],flg[1050000];
int main(void){
	int p1,p2,i,j,len,time[60000],copy[10],f,x,ans,iro;
	char ca[11];
	while(1){
		cin>>ca;
		if(ca[0]=='0') break;
		len=strlen(ca);
		for(i=0;i<len;i++){
			if(ca[i]=='r') que[0][i]=0;
			if(ca[i]=='g') que[0][i]=1;
			if(ca[i]=='b') que[0][i]=2;
		}
		for(i=0;i<=1050000;i++) flg[i]=0;
		p1=0; p2=1; time[0]=0; ans=-1;
		while(1){
			f=1;
			for(i=0;i<len-1;i++){
				if(que[p1][i]!=que[p1][i+1]){
					f=0;
					break;
				}
			}
			if(f==1){
				ans=time[p1];
				break;
			}
			for(i=0;i<len-1;i+=2){
				for(j=0;j<len;j++) copy[j]=que[p1][j];
				if(copy[i]!=copy[i+1]){
					iro=copy[i]+copy[i+1];
					if(iro==3){
						copy[i]=0; copy[i+1]=0;
					}
					if(iro==2){
						copy[i]=1; copy[i+1]=1;
					}
					if(iro==1){
						copy[i]=2; copy[i+1]=2;
					}
				}
				x=copy[0];
				for(j=1;j<len;j++) x=x*4+copy[j];
				if(flg[x]==0){
					flg[x]=1; time[p2]=time[p1]+1;
					for(j=0;j<len;j++) que[p2][j]=copy[j];
					p2++;
				}
			}
			p1++;
		}
		if(ans==-1) cout<<"NA"<<endl;
		else cout<<ans<<endl;
	}
	return 0;
}