#include<iostream>
#include<queue>
#include<string>
#include<map>
using namespace std;
typedef pair<string,int> P;
int main(){
	map<string,int> mp;
	string s,arr,mo;
	int now;
	char c;
	while(cin>>s,s[0]!='0'){
		queue<P> que;
		que.push(P(s,0));
		while(!que.empty()){
			P pre=que.front();
			que.pop();
			now=pre.second;
			arr=pre.first;
			if(mp[arr]==1)
				continue;
			else
				mp[arr]=1;
			int j;
			for(j=1;j<(int)arr.size();j++)
				if(arr[j-1]!=arr[j])
					break;
			if(j==(int)arr.size()){
				cout<<now<<endl;
				goto end;
			}
			for(int i=1;i<(int)arr.size();i++){
				mo=arr;
				if(arr[i-1]!=arr[i]){
					if((arr[i-1]=='b'&&arr[i]=='g')||(arr[i-1]=='g'&&arr[i]=='b'))
						c='r';
					else if((arr[i-1]=='r'&&arr[i]=='g')||(arr[i-1]=='g'&&arr[i]=='r'))
						c='b';
					else c='g';
					mo[i-1]=c;
					mo[i]=c;
					que.push(P(mo,now+1));
				}
			}
		}
		cout<<"NA"<<endl;
		end:
		mp.clear();
	}
	return 0;
}