#include <iostream>
#include <queue>
#include <map>
#include <string>

using namespace std;

typedef pair <string,int> P;

int ans;
string str;

bool f(string s){
	for (int i=1; i<s.size(); i++) {
		if (s[0]!=s[i]) {
			return false;
		}
	}
	return true;
}

char c(char a,char b){
	if (a=='r'&&b=='g'||a=='g'&&b=='r') {
		return 'b';
	}
	else if (a=='r'&&b=='b'||a=='b'&&b=='r') {
		return 'g';
	}
	else {
		return 'r';
	}
}


bool bfs(){
	queue<P> que;
	map<string,int> mat;
	que.push(P(str,0));
	while (que.size()) {
		P p=que.front();
		que.pop();
		
		string s=p.first;
		int n=p.second+1;
		if (mat[s]) {
			continue;
		}
		
		if (f(s)) {
			ans=n-1;
			return true;
		}
		
		mat[s]=n;
		
		for (int i=0; i<s.size()-1; i++) {
			if (s[i]!=s[i+1]) {
				string t=s;
				char u=c(t[i],t[i+1]);
				t[i]=t[i+1]=u;
				que.push(P(t,n));
			}
		}
		
		
		
	}
	return false;
}

int main(){
	
	while (cin>>str&&str!="0") {
		if (bfs()) {
			cout << ans <<endl;
		}
		else {
			cout << "NA" <<endl;
		}
	}
	
}