#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <queue>
#include <set>

using namespace std;

//map<string,bool > passed;
map<string,int> dp;

const int INF=100000000;


int bfs(string str){

	//passed[str]=true;
	set<string> used;
	queue<string> *prv=new queue<string>();
	queue<string> *nxt=new queue<string>();
	int cnt=0;
	prv->push(str);
	while(prv->size()){
		while(prv->size()){
			string s = prv->front();
			prv->pop();
			char cl=s[0];
			bool f=false;
			for(int i = 1; i < s.size(); i++){
				if(s[i]!=cl){
					f=true;
					break;
				}
			}
			if(!f){
				delete prv,nxt;
				return cnt;
			}
			bool flag[200];
			int minCnt=INF;
			for(int i = 0; i < s.size()-1; i++){
				flag['r']=false;
				flag['g']=false;
				flag['b']=false;
				if(s[i]!=s[i+1]){
					flag[s[i]]=true;
					flag[s[i+1]]=true;
					if(!flag['r']){
						string nstr=s;
						nstr[i]='r';
						nstr[i+1]='r';
						if(used.find(nstr)==used.end()){
							used.insert(nstr);
							nxt->push(nstr);
						}
						//minCnt=min(minCnt,dfs(nstr)+1);
//						passed[str]=false;
					}
					else if(!flag['g']){
						string nstr=s;
						nstr[i]='g';
						nstr[i+1]='g';
						if(used.find(nstr)==used.end()){
							used.insert(nstr);
							nxt->push(nstr);
						}
//						minCnt=min(minCnt,dfs(nstr)+1);
//						passed[str]=false;
					}
					else if(!flag['b']){
						string nstr=s;
						nstr[i]='b';
						nstr[i+1]='b';
						if(used.find(nstr)==used.end()){
							used.insert(nstr);
							nxt->push(nstr);
						}
//						passed[str]=true;
	//					minCnt=min(minCnt,dfs(nstr)+1);
	//					passed[str]=false;
					}
				}
			}
		}
		swap(prv,nxt);
		cnt++;
	}
	delete prv,nxt;
	return INF;
}

//int dfs(string str){
//	//if(dp.find(str)!=dp.end()){
//	//	return dp[str];
//	//}
//	if(passed.find(str)!=passed.end()&&passed[str]){
//		return INF;
//	}
////	cout<<str<<endl;
//	char cl=str[0];
//	bool f=false;
//	for(int i = 1; i < str.size(); i++){
//		if(str[i]!=cl){
//			f=true;
//			break;
//		}
//	}
//	if(!f)
//		return 0;
//
//	bool flag[200];
//	int minCnt=INF;
//	for(int i = 0; i < str.size()-1; i++){
//		flag['r']=false;
//		flag['g']=false;
//		flag['b']=false;
//		if(str[i]!=str[i+1]){
//			flag[str[i]]=true;
//			flag[str[i+1]]=true;
//			if(!flag['r']){
//				string nstr=str;
//				nstr[i]='r';
//				nstr[i+1]='r';
//				passed[str]=true;
//				minCnt=min(minCnt,dfs(nstr)+1);
//				passed[str]=false;
//			}
//			else if(!flag['g']){
//				string nstr=str;
//				nstr[i]='g';
//				nstr[i+1]='g';
//				passed[str]=true;
//				minCnt=min(minCnt,dfs(nstr)+1);
//				passed[str]=false;
//			}
//			else if(!flag['b']){
//				string nstr=str;
//				nstr[i]='b';
//				nstr[i+1]='b';
//				passed[str]=true;
//				minCnt=min(minCnt,dfs(nstr)+1);
//				passed[str]=false;
//			}
//		}
//	}
//	//if(minCnt!=INF)
////	dp[str]=minCnt;
//	return minCnt;
//}

int main(){

	string str;
	while(cin>>str&&str!="0"){
		//dp.clear();
		//passed.clear();
		//int ret=dfs(str);
		int ret=bfs(str);
		if(ret!=INF)
			cout<<ret<<endl;
		else
			cout<<"NA"<<endl;
	}


	return 0;
}