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

struct worm{
	int c;
	string s;
};
queue<worm> que;
bool str_check(string str){
	for(int i = 1;i < str.size();++i){
		if(str[0] != str[i]) return false;
	}
	return true;
}
int f(){
	map<string,int> check;
	while(que.size()){
		worm w = que.front(),tmp;
		que.pop();
		int n = w.c;
		string str = w.s;
		if(str_check(str)){
			return n;
		}
		for(int i = 0;i < str.size() - 1;++i){
			if(str[i] != str[i+1]){
				if((str[i] == 'r' && str[i+1] == 'b') || (str[i] == 'b' && str[i+1] == 'r')){
					str[i] = str[i+1] = 'g';
				}
				else if((str[i] == 'g' && str[i+1] == 'b') || (str[i] == 'b' && str[i+1] == 'g')){
					str[i] = str[i+1] = 'r';
				}
				else {
					str[i] = str[i+1] = 'b';
				}

				if(!check.count(str)){
					tmp.s = str;
					tmp.c = n + 1;
					que.push(tmp);
					check[str] = n + 1;
				}
				str = w.s;
			}
		}
	}
	return -1;
}
int main(){
	string str;
	worm w;
	while(cin >> str){
		if(str == "0") break;
		w.s = str;
		w.c = 0;
		que.push(w);
		int n = f();
		if(n == -1) cout << "NA\n";
		else cout << n << endl;
		while(que.size()){
			que.pop();
		}
	}
	return 0;
}