#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <climits>
#include <sstream>
#include <cstdio>
using namespace std;
static const double EPS = 1e-5;
typedef long long ll;


int ans;
set<string> memo;
queue<string> q;
bool na;

void bfs(){
	//cout<<ans<<endl;
	queue<string> nq;
	
	while(!q.empty()){
		string ss=q.front();q.pop();
		if(memo.count(ss)){
			//cout<<ss<<" finded"<<endl;
			continue;
		}
		//cout<<ss<<endl;
		memo.insert(ss);
		bool end=true;
		for(int i=0;i<ss.size()-1;i++)if(ss[i]!=ss[i+1])end=false;
		if(end){
			//cout<<ss<<" "<<ans<<endl;
			return ;
		}

		for(int i=0;i<ss.size()-1;i++){
			if(ss[i]!=ss[i+1]){
				string sss(ss);
				if(ss[i]!= 'r' && ss[i+1]!='r')sss[i]=sss[i+1]='r';
				if(ss[i]!= 'g' && ss[i+1]!='g')sss[i]=sss[i+1]='g';
				if(ss[i]!= 'b' && ss[i+1]!='b')sss[i]=sss[i+1]='b';
				nq.push(sss);
			}
		}
	}
	if(!nq.empty()){
		++ans;
		q=nq;
		bfs();
	}else na=true;
}


main(){
	string ss;
	while(cin>>ss){
		if(ss[0]=='0')break;
		ans=0;
		na=false;
		memo.clear();
		while(!q.empty())q.pop();
		q.push(ss);
		bfs();
		if(na)cout<<"NA"<<endl;
		else cout<<ans<<endl;
	}
}