#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <cstring>
using namespace std;

int ar[11], ag[11], ab[11];
bool checked[59049];
int p3[11];
int change[9] = {0, 8, 4, 8, 4, 0, 4, 0, 8};

int conv(string s) {
	int ret = 0;
	for (int i=0; i<(int)s.size(); ++i) {
		ret *= 3;
		if (s[i] == 'g') ret += 1;
		if (s[i] == 'b') ret += 2;
	}
	return ret;
}

int rotate(int x, int n) {
	int ret = 0;
	for (int i=0; i<n; ++i) {
		ret = ret * 3 + (x % 3 + 1) % 3;
		x /= 3;
	}
	return ret;
}

int main() {
	p3[0] = 1;
	for (int i=1; i<=10; ++i) {
		p3[i] = p3[i-1] * 3;
	}
	ar[0] = ag[0] = ab[0] = 0;
	for (int i=1; i<=10; ++i) {
		ar[i] = ar[i-1];
		ag[i] = ag[i-1] * 3 + 1;
		ab[i] = ab[i-1] * 3 + 2;
	}
	string s;
	while (cin >> s, s != "0") {
		memset(checked, false, sizeof checked);
		int n = s.size();
		int first = conv(s);
		queue<pair<int,int> > q;
		q.push(make_pair(first, 0));
		checked[first] = true;
		int res = -1;
		while ( ! q.empty()) {
			int col = q.front().first;
			int t = q.front().second;
			q.pop();
			if (col == ar[n] || col == ag[n] || col == ab[n]) {
				res = t;
				break;
			}
			for (int i=0; i<n-1; ++i) {
				int replace = change[(col / p3[i]) % 9];
				int nx = (col / p3[i+2]) * p3[i+2] + replace * p3[i] + (col % p3[i]);
				if ( ! checked[nx]) {
					q.push(make_pair(nx, t+1));
					checked[nx] = true; nx = rotate(nx, n);
					checked[nx] = true; nx = rotate(nx, n);
					checked[nx] = true;
				}
			}
		}
		if (res < 0) cout << "NA" << endl;
		else cout << res << endl;
	}
	return 0;
}