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

//#define int long long
#define DEBUG 0
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define dump(o) if(DEBUG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DEBUG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
using pii = pair<int, int>; using vi = vector<int>;
static const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
static const int MOD = (int)(1e9 + 7);

bool f(string s) {
	rep(i, 0, s.size() - 1)
		if (s[i] != s[i + 1])return false;
	return true;
}

signed main() {
	for (string s; cin >> s&&s != "0";) {
		map<string, int> m;
		m[s] = 0;
		queue<string> q;
		q.emplace(s);
		while (!q.empty()) {
			string t = q.front(); q.pop();
			rep(i, 0, t.size() - 1) {
				if (t[i] == t[i + 1])continue;
				string tmp = t;
				if (t[i] + t[i + 1] == 'r' + 'g')tmp[i] = tmp[i + 1] = 'b';
				if (t[i] + t[i + 1] == 'g' + 'b')tmp[i] = tmp[i + 1] = 'r';
				if (t[i] + t[i + 1] == 'b' + 'r')tmp[i] = tmp[i + 1] = 'g';

				if (m.find(tmp) == m.end()) {
					q.emplace(tmp);
					m[tmp] = m[t] + 1;
				}
			}
		}

		int ans = INF;
		for (auto itr = m.begin(); itr != m.end(); itr++) {
			if (f(itr->first))ans=min(ans,itr->second);
		}
		if (ans == INF)cout << "NA" << endl;
		else cout << ans << endl;
	}
	return 0;
}