#include <bits/stdc++.h>
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define INF (1<<29)

map<char, int> m;
map<string, int> ans;

int main() {

	m['r'] = 1;
	m['g'] = 2;
	m['b'] = 4;
	
	string str;
	
	while (cin >> str, str != "0") {
		char c[3] = {'r', 'g', 'b'};
		string ser[3] = {};
		REP(i, 3) REP(j, str.size()) {
			ser[i] += c[i];
		}
		
		queue<pair<int, string> > que;
		REP(i, 3) que.push(make_pair(0, ser[i]));
		
		while (!que.empty()) {
			int t = que.front().first;
			string now = que.front().second;
			que.pop();
			
			if (ans.find(now) != ans.end()) continue;
			ans[now] = t;
			if (now == str) break;
			
			REP(i, now.size() - 1) {
				if (now[i] == now[i + 1]) {
					string next = now;
					int nextcor = 7 - m[now[i]];
					vector<char> pl;
					REP(j, 3) if (nextcor & (1<<j)) pl.push_back(c[j]);
					REP(j, 2) {
						next[i] = pl[j];
						next[i + 1] = pl[(j + 1) % 2];
						que.push(make_pair(t + 1, next)); 
					}
				}
			}
		}
		if (ans.find(str) == ans.end()) puts("NA");
		else cout << ans[str] << endl;
	}
	return 0;
}