#include <iostream>
#include <string>
#include <queue>
#include <map>
using namespace std;

char kagasan(char A,char B){
	if(A=='r'&&B=='g')return 'b';
	if(A=='r'&&B=='b')return 'g';
	if(A=='g'&&B=='r')return 'b';
	if(A=='g'&&B=='b')return 'r';
	if(A=='b'&&B=='g')return 'r';
	if(A=='b'&&B=='r')return 'g';
}

int main(){
	string STR;
	while(cin>>STR){
		if(STR=="0")break;
		map<string,int>time;
		queue<string>name;
		name.push(STR);
		time[STR]=1;
		int flag=1;
		while(name.empty()==0){
			int mini=1;
			string s=name.front();
			for(int i=0;i<s.size()-1;i++){
				if(s[i]!=s[i+1]){
					mini=0;
					string ka=s;
					ka[i]=kagasan(s[i],s[i+1]);
					ka[i+1]=kagasan(s[i],s[i+1]);
					if(time[ka]==0){
						time[ka]=time[s]+1;
						name.push(ka);
						
					}
				}
			}
			if(mini){
				cout<<time[name.front()]-1<<endl;
				flag=0;
				break;
			}
			name.pop();
		}
		if(flag)cout<<"NA"<<endl;
	}
	return 0;
}
