#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;
using namespace std;

char z[3]={'r','b','g'};

int Unzip(string s){
  int ans=0;
  for(int i=0;i<s.size();i++){
    ans*=3;
    for(int j=0;j<3;j++){
      if(s[i]==z[j])ans+=j;
    }
  }
  return ans;
}
char Other(char a,char b){
  for(int i=0;i<3;i++){
    if(z[i]!=a&&z[i]!=b)return z[i];
  }
  return '#';
}

int dis[60000];
queue<pair<string,int> >Q;
int main(){
  string s;
  while(cin>>s&&s!="0"){
    lol(i,60000)dis[i]=mod;
    Q.push(make_pair(s,0));
    while(!Q.empty()){
      string x=Q.front().first;
      int len=Q.front().second;
      Q.pop();
      int index=Unzip(x);
      if(dis[index]<=len)continue;
      dis[index]=len;
      for(int i=0;i<x.size()-1;i++){
	if(x[i]!=x[i+1]){
	  string news=x;
	  news[i]=Other(x[i],x[i+1]);
	  news[i+1]=Other(x[i],x[i+1]);
	  Q.push(make_pair(news,len+1));
	}
      }
    }
    int ans=mod;
    for(int i=0;i<3;i++){
      for(int j=0;j<s.size();j++)s[j]=z[i];
      int index=Unzip(s);
      ans=min(ans,dis[index]);
    }
    if(ans==mod)cout<<"NA"<<endl;
    else cout<<ans<<endl;
  }
  return 0;
}