#include<cstdio>
#include<algorithm>
#include<string>
#include<vector>
#include<iostream>
#include<map>
#include<queue>

using namespace std;

#define rep(i,n) for(int i=0;i<int(n);i++)
#define reps(i,n) for(int i=1;i<=int(n);i++)

class S{
public:
  string s;
  int n;
  S(string s,int n):s(s),n(n){}
};

int main(){
  while(1){
    string a;
    cin>>a;
    if(a=="0")break;

    queue<S> que;
    map<string,int> memo;
    char cc[111][111];
    rep(i,111)rep(j,111)cc[i][j]=-1;
    que.push(S(a,0));
    int ans=0;
    int kn=0;
    while(1){
      if(que.empty()==1){
	break;
      }
      S u = que.front();
      que.pop();
      ans=u.n;
      //cout<<u.s<<" "<<u.n<<endl;
      if(memo[u.s]!=0){
	continue;
      }
      memo[u.s]=1;
      int comp=1;
      int ch=u.s[0];
      reps(i,u.s.size()-1){
	if(ch!=u.s[i]){
	  comp=0;
	  break;
	}
      }
      if(comp==1){
	kn=1;
	break;
      }
      cc['r']['g']=cc['g']['r']='b';
      cc['r']['b']=cc['b']['r']='g';
      cc['b']['g']=cc['g']['b']='r';
      rep(i,u.s.size()-1){
	string cop=u.s;
	if(u.s[i]!=u.s[i+1]){
	  cop[i]=cop[i+1]=cc[cop[i]][cop[i+1]];
	  que.push(S(cop,u.n+1));
	}
      }
    }
    if(kn==1){
      printf("%d\n",ans);
    }else{
      printf("NA\n");
    }
  }
}