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

using namespace std;

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

char Check_Color(char c1, char c2) {
	if (c1 < c2) {
		swap(c1,c2);
	}
	if (c1 == 'r') {
		if (c2 == 'g') {
			return 'b'; 
		}
		else {
			return 'g';
		}
	}
	return 'r';
}

int main(void) {
	string str,ss;
	cin >> str;
	while (str != "0") {
		int len = str.length();
		map<string,bool> ob;
		ob[str] = true;

		queue<string> warm;
		queue<int> deep;
		warm.push(str);
		deep.push(0);
		bool find = false;
		int d;
		int ret = -1;
		while (!find && !warm.empty()) {
			str = warm.front();
			d = deep.front();
			warm.pop();
			deep.pop();
			if (Check_Warm_Color(str)) {
				ret = d;
				find = true;
			}
			else {
				for (int i = 0; i < str.length() - 1; ++i) {
					ss = str;
					if (str[i] != str[i+1]) {
						char temp = Check_Color(str[i],str[i+1]);
						ss[i] = temp;
						ss[i+1] = temp;
					}
					if (!ob[ss]) {
						ob[ss] = true;
						warm.push(ss);
						deep.push(d+1);
					}
				}
			}
		}
		if (ret < 0) {
			cout << "NA" << endl;
		}
		else {
			cout << ret << endl;
		}

		cin >> str;
	}
	return 0;
}