#include<iostream>
#include<cstring>
#include<algorithm>
#include<math.h>
#include<map>
#include<queue>

using namespace std;

string InputStr, StrNow;
map<string, int> DpResult;


bool isAllSame() {
	int size;

	size = StrNow.size();
	for (int i = 1; i < size; i++) {
		if (StrNow[0] != StrNow[i]) {
			return false;
		}
	}
	return true;
}

bool solve() {
	int size;
	string strPrev;
	queue<string> CurrentStr;

	DpResult[InputStr] = 0;
	CurrentStr.push(InputStr);

	while (!CurrentStr.empty()) {
		StrNow = strPrev = CurrentStr.front();
		CurrentStr.pop();

		//cout << "befor:" << strPrev << endl;
		size = StrNow.size() - 1;
		for (int i = 0; i < size; i++) {
			StrNow = strPrev;
			if ((StrNow[i] == 'r' && StrNow[i + 1] == 'g') || (StrNow[i] == 'g' && StrNow[i + 1] == 'r')) {
				StrNow[i] = StrNow[i + 1] = 'b';
			}
			else if ((StrNow[i] == 'r' && StrNow[i + 1] == 'b') || (StrNow[i] == 'b' && StrNow[i + 1] == 'r')) {
				StrNow[i] = StrNow[i + 1] = 'g';
			}
			else if ((StrNow[i] == 'g' && StrNow[i + 1] == 'b') || (StrNow[i] == 'b' && StrNow[i + 1] == 'g')) {
				StrNow[i] = StrNow[i + 1] = 'r';
			}

			//cout << "after:" << StrNow << endl;
			if (DpResult.find(StrNow) == DpResult.end()) {
				CurrentStr.push(StrNow);
				DpResult[StrNow] = DpResult[strPrev] + 1;
			}

			if (isAllSame()) {
				return true;
			}
		}
	}

	return false;
}

int main() {

	while (cin >> InputStr, InputStr[0] != '0') {
		//cout << InputStr << endl;
		DpResult.clear();		
		if (solve()) {
			cout << DpResult[StrNow] << endl;
		}
		else {
			cout << "NA" << endl;
		}
	}

	return 0;
}


