#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") {
		
		queue<pair<int, string> > que;
		que.push(make_pair(0, str));
		
		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;
			
			REP(i, now.size() - 1) {
				if (now[i] != now[i + 1]) {
					string next = now;
					int nextcor = 7 - m[now[i]] - m[now[i + 1]];
					switch (nextcor) {
					case 1: next[i] = next[i + 1] = 'r'; break;
					case 2: next[i] = next[i + 1] = 'g'; break;
					case 4: next[i] = next[i + 1] = 'b'; break;
					}
					que.push(make_pair(t + 1, next));
				}
			}
		}
		char c[3] = {'r', 'g', 'b'};
		string ser[3] = {};
		REP(i, 3) REP(j, str.size()) {
			ser[i] += c[i];
		}
		int miner = INF;
		REP(i, 3) if (ans.find(ser[i]) != ans.end()) miner = min(miner, ans[ser[i]]);
		if (miner == INF) puts("NA");
		else cout << miner << endl;
	}
	return 0;
}