#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int dist[60000];
vector<int> x[60000];
string S; queue<int>Q;
int power[12], p2[12];
int main() {
	power[0] = 1; p2[0] = 1;
	for (int i = 1; i < 12; i++)power[i] = power[i - 1] * 3;
	for (int i = 1; i < 12; i++)p2[i] = p2[i - 1] + power[i];
	while (true) {
		cin >> S; if (S == "0") break;
		int bit[12], c[12], D = 0;
		for (int i = 0; i < S.size(); i++) {
			if (S[i] == 'r')D += 0 * power[i];
			if (S[i] == 'g')D += 1 * power[i];
			if (S[i] == 'b')D += 2 * power[i];
		}
		for (int i = 0; i < 60000; i++) {
			dist[i] = 99999; x[i].clear();
		}
		for (int i = 0; i < power[S.size()]; i++) {
			for (int j = 0; j < S.size(); j++)bit[j] = (i / power[j]) % 3;
			for (int j = 0; j < S.size() - 1; j++) {
				for (int k = 0; k < S.size(); k++)c[k] = bit[k];
				if (bit[j] != bit[j + 1]) {
					int V = bit[j] + bit[j + 1];
					V = 3 - V; c[j] = V; c[j + 1] = V;
					int T = 0;
					for (int k = 0; k < S.size(); k++) {
						T += c[k] * power[k];
					}
					x[i].push_back(T);
				}
			}
		}
		Q.push(D); dist[D] = 0;
		while (!Q.empty()) {
			int a = Q.front(); Q.pop();
			for (int i = 0; i < x[a].size(); i++) {
				if (dist[x[a][i]] == 99999) {
					dist[x[a][i]] = dist[a] + 1;
					Q.push(x[a][i]);
				}
			}
		}
		int minx = min(dist[0], min(dist[p2[S.size() - 1]], dist[2 * p2[S.size() - 1]]));
		if (minx == 99999)cout << "NA" << endl;
		else cout << minx << endl;
	}
	return 0;
}