#include<iostream>
using namespace std;
#include<cstdio>
#include<map>
#include<queue>
#include<string>
#include<algorithm>
#include<cstring>

typedef pair<string,int> P;

int main(){
  int kaku=0;
  string body;
  while(1){
  cin>>body;
  if(body=="0")return 0;
  map<string,int> used;
  queue<P> que;
  que.push(P(body,0));
  while(!que.empty()){
    P p =que.front();que.pop();
    string now = p.first;
    int co = p.second;
    int c=1;
    for(int i=0;i<body.size();i++){
      if(now[0]==now[i+1])c++;
    }
    if(c==body.size()){
      cout<<co<<endl;
      kaku=1;
      break;
    }
    if(used[now]==1)continue;
    used[now]=1;
    for(int i=0;i<body.size()-1;i++){
      string next=now;
    if(next[i]==next[i+1])continue;
    if((next[i]=='r' && next[i+1]=='b') || (next[i]=='b' && next[i+1]=='r')){
      next[i]='g';
      next[i+1]='g';
      que.push(P(next,co+1));
    }
    if((next[i]=='r' && next[i+1]=='g') || (next[i]=='g' && next[i+1]=='r')){
      next[i]='b';
      next[i+1]='b';
      que.push(P(next,co+1));
    }
    if((next[i]=='g' && next[i+1]=='b') || (next[i]=='b' && next[i+1]=='g')){
      next[i]='r';
      next[i+1]='r';
      que.push(P(next,co+1));
    }
  }
  }
  if(kaku==0)cout<<"NA"<<endl;
  kaku=0;
}
}