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

using namespace std;

map<string, char> rule = { 
	{"rb", 'g'},
	{"br", 'g'},
	{"rg", 'b'},
	{"gr", 'b'},
	{"gb", 'r'},
	{"bg", 'r'} };

bool isjudge(string s){
	bool r = true;
	char c = s[0];
	for(int i = 0;i < s.length();++i){
		r &= (c == s[i]);
	}
	return r;
}

int bfs(string s){
	queue<string> q;
	map<string, int> v;
	v[s] = 0;
	q.push(s);
	while(!q.empty()){
		string t = q.front(), n;
		char c;
		q.pop();
		if(isjudge(t)) return v[t];
		for(int i = 0;i < (t.length() - 1);++i){
			if(t[i] != t[i + 1]){
				n = t;
				c = rule[t.substr(i, 2)];
				n[i] = n[i + 1] = c;
				if(v.count(n) == 0){
					q.push(n);
					v[n] = v[t] + 1;
				}
			}
		}
	}
	return -1;
}

int main(){
	string s;
	int c;
	while(cin >> s){
		if(s == "0") break;
		else {
			c = bfs(s);
			if(c == -1) cout << "NA" << endl;
			else cout << c << endl;
		}
	}
	return 0;
}

