#include<iostream>
#include<queue>
#include<set>
using namespace std;

typedef pair<string,int> P;

int main()
{
  for(;;)
    {
      string str;
      cin>>str;
      if(str=="0")
	break;
      queue<P> qu;
      set<string> hash;       
      qu.push(P(str,0));
      hash.insert(str);
      int ans=-1;
      while(!qu.empty())
	{
	  P a= qu.front();
	  qu.pop();
	  int count=0;
	 
	  string t=a.first;
	  for(int i=0;i<t.size()-1;i++)
	    {
	      if(t[i]!=t[i+1])
		{
		  string x=t; 
		  if((x[i]=='r'&&x[i+1]=='g') ||(x[i]=='g'&&x[i+1]=='r'))
		    x[i]='b',x[i+1]='b';
		  if((x[i]=='r'&&x[i+1]=='b') ||(x[i]=='b'&&x[i+1]=='r'))
		    x[i]='g',x[i+1]='g';
		  if((x[i]=='g'&&x[i+1]=='b') ||(x[i]=='b'&&x[i+1]=='g'))
		    x[i]='r',x[i+1]='r';
		  if(hash.find(x)==hash.end())
		    {
		      hash.insert(x);
		      qu.push(P(x,a.second+1));
		    }
		}
	      else
		{
		  count++;
		}
	    }
	  if(count==t.size()-1)
	    {
	      ans=a.second;
	      break;
	    }
	}
      if(ans==-1)
	  cout<<"NA"<<endl;            
	else
	  cout<<ans<<endl;            
    }

}