#include<iostream>
#include<queue>
#include<map>
using namespace std;
string S;
char f(char a,char b)
{
	if(a=='r'&&b=='b')return 'g';
	else if(a=='r'&&b=='g')return 'b';
	else if(a=='b'&&b=='r')return 'g';
	else if(a=='b'&&b=='g')return 'r';
	else if(a=='g'&&b=='r')return 'b';
	else return 'r';
}
main()
{
	while(cin>>S,S!="0")
	{
		queue<pair<int,string> >P;
		P.push(make_pair(0,S));
		map<string,bool>M;
		M[S]=1;
		bool flag=1;
		while(!P.empty())
		{
			int u=P.front().first;
			string s=P.front().second;
			P.pop();
			bool F=0;
			for(int i=0;i<s.size()-1;i++)
			{
				if(s[i]==s[i+1])continue;
				F=1;
				string t=s;
				t[i]=t[i+1]=f(s[i],s[i+1]);
				if(!M[t])
				{
					M[t]=1;
					P.push(make_pair(u+1,t));
				}
			}
			if(!F)
			{
				cout<<u<<endl;
				flag=0;
				break;
			}
		}
		if(flag)cout<<"NA"<<endl;
	}
}

