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


class Worm {
public:
	string str;
	int turn;
	Worm(string st, int t) : str(st), turn(t) {}
};

Worm nWorm(Worm w, int p) {
	if (w.str[p] > w.str[p+1]) {
		char t=w.str[p];
		w.str[p] = w.str[p+1];
		w.str[p+1] = t;
	}

	if (w.str[p]=='b' && w.str[p+1]=='g') w.str[p] = w.str[p+1] = 'r';
	else if (w.str[p]=='b' && w.str[p+1]=='r') w.str[p] = w.str[p+1] = 'g'; 
	else if (w.str[p]=='g' && w.str[p+1]=='r') w.str[p] = w.str[p+1] = 'b';

	w.turn++;
	return w;
}

int main() {
	string str;
	while (cin >> str, str[0]!='0') {
		queue<Worm> q;
		Worm init(str, 0);
		q.push(init);
		bool f=false, fl;
		set<string> s;
		s.insert(str);

		while (!q.empty()) {
			Worm tmp = q.front(); q.pop();
			for (int i=0; i<tmp.str.size()-1; i++) {
				Worm next = nWorm(tmp, i);
				if (s.insert(next.str).second) q.push(next);
			}

			fl = true;
			char c = tmp.str[0];
			for (int i=1; i<tmp.str.size(); i++)
				if (tmp.str[i] != c) { fl=false; break; }

			if (fl) { cout << tmp.turn << endl; f=true; break; }
		}

		if (!f) cout << "NA" << endl;
	}
	return 0;
}