
#include<iostream>
#include<string>
#include<queue>
#include<map>
using namespace std;
struct Data{string s;int n;};
int main()
{
  map<int,int> change;
  change['r'+'g']='b';
  change['g'+'b']='r';
  change['b'+'r']='g';
  map<string,int> changed;
  queue<Data> q;
  string s;
  Data d;
  int i,n;
  bool flag;
  int t=0;
  while(cin>>s,s!="0"){
    changed.clear();
    while(!q.empty())q.pop();
    d.s=s;
    d.n=0;
    q.push(d);
    changed[d.s]=1;
    while(!q.empty()){
      d=q.front();
      s=d.s;
      n=d.n;
      q.pop();
      flag=true;
      for(i=1;i<s.size();i++){
	if(s[i-1]==s[i])continue;
	flag=false;
	d.s=s;
	d.s[i-1]=d.s[i]=change[d.s[i-1]+d.s[i]];
	d.n=n+1;
	if(changed.find(d.s)!=changed.end())continue;
	changed[d.s]=1;
	q.push(d);
      }
      if(flag)break;
    }
    if(flag)cout<<n<<endl;
    else puts("NA");
  }
}