#include <iostream>
#include <queue>
#include <set>
using namespace std;

class Info{
public:
	string s;
	int depth;
};

bool is_answer(string s){
	for(int i=1;i<s.length();i++){
		if(s.at(0) != s.at(i)) return false;
	}
	return true;
}

string change_color(string s, int i){
	char f = s.at(i);
	char b = s.at(i+1);

	if(f == 'r' && b == 'g' || f == 'g' && b == 'r'){
		s.replace(i,2,"bb");
	}
	else if(f == 'r' && b == 'b' || f == 'b' && b == 'r'){
		s.replace(i,2,"gg");
	}
	else if(f == 'g' && b == 'b' || f == 'b' && b == 'g'){
		s.replace(i,2,"rr");
	}

	return s;
}

int bfs(string s){
	int len = s.length();
	set<string> worm_set;
	queue<Info> q;
	Info tmp = {s,0};

	if(is_answer(s)){
		return 0;
	}

	q.push(tmp);
	worm_set.insert(s);

	while(!q.empty()){
		tmp = q.front(); q.pop();

		for(int i=0;i<len-1;i++){
			string next_worm = change_color(tmp.s,i);

			if(is_answer(next_worm)){
				return tmp.depth + 1;
			}

			if(next_worm != tmp.s &&
				 worm_set.find(next_worm) == worm_set.end()){
				Info next_info = {next_worm, tmp.depth + 1};

				q.push(next_info);
				worm_set.insert(next_worm);
			}
		}
	}

	return -1;
}

int main(void){
	string s;

	while(cin >> s && s != "0"){
		int ans = bfs(s);

		if(ans >= 0){
			cout << ans << endl;
		}
		else{
			cout << "NA\n";
		}
	}

  return 0;
}