#include<stdio.h>
#define M 1000000000
int l;
int d[110][60000]={0};
void f(int n,int *a){//kakunou
  int i;
  for(i=0;i<l;n/=3)a[i++]=n%3;
}
int g(int *a){
  int n=0,i;
  for(i=l;i;i--)n=n*3+a[i-1];
}
int zMIN(int a,int b){
  if(b==0)return a;
  if(a==0||a>b)return b;
  return a;
}
int main(){
  int i,j,k,n,a[20];
  char s[20];
  while(scanf("%s",s),s[1]){
    for(i=0;i<110;i++){
      for(j=0;j<60000;j++)d[i][j]=0;
    }
    for(l=n=0;s[l];l++){
      if(s[l]=='r')n=n*3+0;
      if(s[l]=='g')n=n*3+1;
      if(s[l]=='b')n=n*3+2;
    }
    d[0][n]=1;
    for(i=n=0;i<l;i++)n=n*3+2;//printf("%d\n",n);
    for(i=0;i<100;i++){
      for(j=0;j<n;j++){
	if(d[i][j]==0)continue;
	d[i+1][j]=zMIN(d[i+1][j],d[i][j]);
	for(k=1;k<l;k++){
	  f(j,a);
	  a[k]=a[k-1]=(6-a[k]-a[k-1])%3;
	  d[i+1][g(a)]=zMIN(d[i+1][g(a)],d[i][j]+1);
	}
      }
    }
    d[100][0]=zMIN(d[100][0],zMIN(d[100][n/2],d[100][n]));
    if(d[100][0])printf("%d\n",d[100][0]-1);
    else         printf("NA\n");
  }
  return 0;
}