#include<stdio.h>
#include<queue>
#include<string.h>

using namespace std;
char c[11];
int d[10];
int bfs[59049];
int temp[10];
int main(){
	while(1){
		scanf("%s",c);
		if(c[0]=='0')return 0;
		queue<int> Q;
		for(int i=0;i<59049;i++)bfs[i]=-1;
		int first=0;
		int s=strlen(c);
		for(int i=0;i<s;i++){
			first*=3;
			if(c[i]=='r')first+=2;
			if(c[i]=='g')first++;
		}
		bfs[first]=0;
		Q.push(first);
		while(Q.size()){
			int now=Q.front();
			int val=now;
			for(int i=0;i<s;i++){
				d[s-i-1]=val%3;
				val/=3;
				temp[s-i-1]=d[s-i-1];
			}
			for(int i=0;i<s-1;i++){
				if(d[i]!=d[i+1]){
					if(d[i]!=0&&d[i+1]!=0){
						temp[i]=temp[i+1]=0;
						int next=0;
						for(int j=0;j<s;j++){
							next*=3;
							next+=temp[j];
						}
						if(bfs[next]==-1){
							bfs[next]=bfs[now]+1;
							Q.push(next);
						}
					}
					if(d[i]!=1&&d[i+1]!=1){
						temp[i]=temp[i+1]=1;
						int next=0;
						for(int j=0;j<s;j++){
							next*=3;
							next+=temp[j];
						}
						if(bfs[next]==-1){
							bfs[next]=bfs[now]+1;
							Q.push(next);
						}
					}
					if(d[i]!=2&&d[i+1]!=2){
						temp[i]=temp[i+1]=2;
						int next=0;
						for(int j=0;j<s;j++){
							next*=3;
							next+=temp[j];
						}
						if(bfs[next]==-1){
							bfs[next]=bfs[now]+1;
							Q.push(next);
						}
					}
					temp[i]=d[i];
					temp[i+1]=d[i+1];
				}
			}
			Q.pop();
		}
		int q=0;
		for(int i=0;i<s;i++){
			q*=3;
			q++;
		}
		int r=0;
		for(int i=0;i<s;i++){
			r*=3;
			r+=2;
		}
		int ans=99999999;
		if(bfs[0]!=-1&&ans>bfs[0])ans=bfs[0];
		if(bfs[q]!=-1&&ans>bfs[q])ans=bfs[q];
		if(bfs[r]!=-1&&ans>bfs[r])ans=bfs[r];
		if(ans==99999999)printf("NA\n");
		else printf("%d\n",ans);
	}
}