#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;i++)
using namespace std;

char dir[]{ 'r','g','b' };
int main() {
	string s;
	while (cin >> s, s != "0") {
		queue<string>que;
		unordered_map<string, int>mp;
		que.push(s);
		mp[s] = 1;
		while (!que.empty()) {
			string u = que.front(); que.pop();
			int r, g;
			if ((r = count(u.begin(), u.end(), 'r')) == u.size() ||
				(r == 0 && (g = count(u.begin(), u.end(), 'g')) == u.size()) ||
				(r == 0 && g == 0)) {
				printf("%d\n", mp[u] - 1);
				goto goal;
			}
			rep(i, u.size() - 1) {
				if (u[i] != u[i + 1]) {
					string v = u;
					v[i] = v[i + 1] = dir[3 - (find(dir, dir + 3, u[i]) - dir) - (find(dir, dir + 3, u[i + 1]) - dir)];
					if (!mp[v]) {
						mp[v] = mp[u] + 1;
						que.push(v);
					}
				}
			}
		}
		puts("NA");
	goal:;
	}
}