#include <iostream>
#include <map>
#include <queue>
#include <string>
using namespace std;
map<char, map<char, char> > convert;

void solve(const string& s) {
	map<string, int> visited;
	queue<string> que;
	visited[s] = 0;
	que.push(s);
	while (!que.empty()) {
		string current = que.front();
		que.pop();
		if (current == string(current.size(), current[0])) {
			cout << visited[current] << endl;
			return;
		}
		for (unsigned i = 0; i < current.size() - 1; i++) {
			if (current[i] != current[i + 1]) {
				char c = convert[current[i]][current[i + 1]];
				string next = current;
				next[i] = next[i + 1] = c;
				if (visited.find(next) != visited.end()) continue;
				visited[next] = visited[current] + 1;
				que.push(next);
			}
		}
	}
	cout << "NA" << endl;
}

int main() {
	convert['r']['g'] = 'b';
	convert['g']['r'] = 'b';
	convert['r']['b'] = 'g';
	convert['b']['r'] = 'g';
	convert['b']['g'] = 'r';
	convert['g']['b'] = 'r';
	string str;
	while (cin >> str, str != "0") {
		solve(str);
	}
}