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

#define mkp(x, y) (make_pair(x, y))

int main() {
	string in;

	while(cin >> in, in != "0") {
		set<string> appeared;
		queue<pair<string, int> > q;
		int loop_flag = -1;

		appeared.insert(in);
		q.push(mkp(in, 0));

		while(!q.empty()) {
			string worm;
			int count;
			pair<string, int> p;
			bool complete_flag = true;
			p = q.front(); q.pop();
			worm = p.first;
			count = p.second;

			for(int i = 1; i < worm.size(); i++) {
				if(worm[i - 1] != worm[i]) {
					string tmp(worm);
					tmp[i - 1] = tmp[i] = 'r' + 'g' + 'b' - worm[i - 1] - worm[i];
					if(appeared.find(tmp) == appeared.end()) {
						q.push(mkp(tmp, count + 1));
						appeared.insert(tmp);
					}
					complete_flag = false;
				}
			}

			if(complete_flag) {
				loop_flag = count;
				break;
			}
		}

		if(loop_flag != -1)
			cout << loop_flag << endl;
		else
			cout << "NA" << endl;
	}

	return 0;
}