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

using namespace std;

typedef pair <string, int> P;

#define mp(a, b) make_pair(a, b)

char diff(char a, char b)
{
	if (a != 'r' && b != 'r') return 'r';
	if (a != 'g' && b != 'g') return 'g';
	if (a != 'b' && b != 'b') return 'b';
	return 'a';
}

bool check(string str)
{
	char c = str[0];
	for (int i = 0; i < str.length(); i++){
		if (c != str[i]) return false;
	}

	return true;
}

int main(void)
{
	string str;

	while (cin >> str){
		if (str == "0") return 0;

		int ret = -1, a;
		queue < P > q;
		map <string, bool> memo;
		q.push(mp(str, 0));
		while (!q.empty()){
			P now = q.front();
			q.pop();
			if (memo[now.first]){
				continue;
			}
			memo[now.first] = true;
			if (check(now.first)){
				ret = now.second;
				break;
			}
			for (int i = 0; i < now.first.length()-1; i++){
				if (now.first[i] != now.first[i + 1]){
					string tmp = now.first;
					tmp[i] = diff(now.first[i], now.first[i + 1]);
					tmp[i + 1] = diff(now.first[i], now.first[i + 1]);
					q.push(mp(tmp, now.second + 1));
				}
			}
		}

		if (ret >= 0) cout << ret << endl;
		else cout << "NA" << endl;
	}

	return 0;
}