#include<vector>
#include<string>
#include<set>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
bool ck(string &s){
	rep(k,s.size()-1)if(s[k]!=s[k+1])return 0;
	return 1;
}
int main(){
	string s;
	while(cin>>s,s!="0"){
		int step=0; bool sc=ck(s);
		vector<string> frontier,next;
		frontier.push_back(s);
		set<string> visited; visited.insert(s);
		for(bool cg=1;cg&&!sc;step++){
			cg=0; next.clear();
			rep(i,frontier.size()){
				rep(j,frontier[i].size()-1){
					char c,cc=frontier[i][j],cn=frontier[i][j+1];
					if(cc==cn)continue;
					if(cc>cn)swap(cc,cn);
					if(cc=='b')c=cn=='g'?'r':'g';
					else c='b';
					
					string nx=frontier[i];
					nx[j]=nx[j+1]=c;
					if(visited.find(nx)==visited.end()){
						cg=1;
						sc=sc||ck(nx);
						next.push_back(nx),visited.insert(nx);
					}
				}
			}
			frontier=next;
		}
		if(sc)cout<<step<<endl;
		else cout<<"NA"<<endl;
	}
	return 0;
}