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

#define QUEUE_NUM (10192)

struct Data{
	char color[15];
	int cnt;
};

typedef struct {
	int top,bottom;
	Data data[QUEUE_NUM];
}Queue;

//QÉdataðÇÁ
void push(Queue* Q, Data data){
	Q->data[Q->bottom] = data;
	Q->bottom = (Q->bottom +1);
}

//QÌæªvfðæ¾
Data front(Queue* Q)
{
	return Q->data[Q->top];
}

//QÌæªvfðí
void pop(Queue* Q)
{
	Q->top = (Q->top + 1) %QUEUE_NUM;
}

int check(char str[],int n){
	int i,number,tem=1,temp;
	for(i=0;i<n;i++){
		if(str[i]=='r'){
			str[i]='0';
		}
		else if(str[i]=='g'){
			str[i]='1';
		}
		else if(str[i]=='b'){
			str[i]='2';
		}
		else{
			str[i]='\0';
		}
	}
	
	number = atoi(str);
//	puts("\n--in--");
//	printf("%d  ",number);
	number=0;
	while(i!=-1){
		temp = (str[i]-48);
		number += tem*temp;
		tem*=3;
		i--;
	}
//	printf("%d\n",number);
//	puts("--o--");
	return number;
}

int main(void)
{
	while(1){
		int i,j,n,ans=-1;
		char col[4]={'r','g','b'},str[16];
		int temp;
		bool visited[178000]={0};
		Queue Q = {0,0,{0}};
		Data bag;
		
		scanf("%s",bag.color);
		if(bag.color[0]=='0')break;
		n = strlen(bag.color);
		bag.cnt=0;
		push(&Q,bag);
		
		while(!(Q.bottom==Q.top)){
			int flg=0,flag=0;
			Data d = front(&Q); 
			pop(&Q);
			
			
			for(i=0;i<n-1;i++){
				if(d.color[i]!=d.color[i+1])flg=1;
			}
			if(flg==0){
				ans=d.cnt;
				break;
			}
			
			for(i=0;i<n-1;i++){
				if(d.color[i] != d.color[i+1]){
					int used[4]={0};
					Data next;
					flg=0;
					strcpy(next.color ,d.color);
					
					for(j=0;j<3;j++){
						if(col[j]==next.color[i])used[j]=1;
						if(col[j]==next.color[i+1])used[j]=1;
					}
					
					for(j=0;j<3;j++){
						if(used[j]==0){
							next.color[i]=col[j];
							next.color[i+1]=col[j];
						}
					}
					
					/**/
					strcpy(str,next.color);
					temp=check(str,n);
					
					if(visited[temp]==1){
				//		printf("d¡\n");
						continue;
					}
					else {
						visited[temp]=1;
					}
					
					/**/
	//				printf("now%d == %s\n",next.cnt,next.color);
				//	Sleep(100);
					next.cnt = d.cnt+1;
					push(&Q,next);
				}
			}
		}
		if(ans==-1){
			puts("NA");
		}
		else {
			printf("%d\n",ans);
		}
	}
	return 0;
}