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

struct Bug{
	int red, blue, green, days;
	std::string body;
};

int main(){
	std::string s;
	while(std::cin >> s, s != "0"){
		int bug_length = s.length();
		std::queue<Bug> bug_s;
		std::map<std::string, int> bug_m;
		Bug first_bug = {0, 0, 0, 0, s};
		for(int i=0;i<s.length();i++){
			if(s[i] == 'r'){
				first_bug.red++;
			}
			if(s[i] == 'g'){
				first_bug.green++;
			}
			if(s[i] == 'b'){
				first_bug.blue++;
			}
		}
		bug_s.push(first_bug);
		int res = -1;
		while(!bug_s.empty()){
			Bug b = bug_s.front();bug_s.pop();
			if(bug_m[b.body] > 0){
				continue;
			}
			if(b.red == bug_length || b.blue == bug_length || b.green == bug_length){
				res = b.days;
				break;
			}
			Bug temp;
			for(int i=0;i<bug_length-1;i++){
				temp = b;
				if(temp.body[i] != temp.body[i+1]){
					if(temp.body[i]+temp.body[i+1] == 'r'+'b'){
						temp.body[i] = temp.body[i+1] = 'g';
						temp.red--;temp.blue--;temp.green+=2;
					}else if(temp.body[i]+temp.body[i+1] == 'r'+'g'){
						temp.body[i] = temp.body[i+1] = 'b';
						temp.red--;temp.green--;temp.blue+=2;
					}else{
						temp.body[i] = temp.body[i+1] = 'r';
						temp.blue--;temp.green--;temp.red+=2;
					}
					temp.days++;
					bug_s.push(temp);

				}
			}
			bug_m[b.body]++;
		}

		if(res != -1){
			std::cout << res << std::endl;
		}else{
			std::cout << "NA\n";
		}
	}
}