#include <queue>
#include <string>
#include <cstring>
#include <iostream>
using namespace std;
int dp[60000];
int hash_(string s) {
	int ret = 0;
	for(int i = 0; i < s.size(); i++) {
		ret *= 3;
		if(s[i] == 'g') ret += 1;
		if(s[i] == 'b') ret += 2;
	}
	return ret;
}
string s; int w, w2;
int main() {
	while(cin >> s, s != "0") {
		memset(dp, -1, sizeof(dp)); w = 0, w2 = 1;
		for(int i = 0; i < s.size(); i++) w += w2, w2 *= 3;
		int h2 = hash_(s); dp[h2] = 0;
		if(h2 % w == 0) {
			printf("0\n"); continue;
		}
		queue<string> que; que.push(s); bool flag = false;
		while(!que.empty()) {
			string t = que.front(); que.pop(); int h_ = hash_(t);
			for(int i = 1; i < t.size(); i++) {
				if(t[i - 1] != t[i]) {
					string u = t;
					if(t[i - 1] != 'r' && t[i] != 'r') u[i - 1] = 'r', u[i] = 'r';
					else if(t[i - 1] != 'g' && t[i] != 'g') u[i - 1] = 'g', u[i] = 'g';
					else u[i - 1] = 'b', u[i] = 'b';
					int h = hash_(u);
					if(h % w == 0) {
						printf("%d\n", dp[h_] + 1); flag = true; break;
					}
					if(dp[h] == -1) {
						dp[h] = dp[h_] + 1; que.push(u);
					}
				}
			}
			if(flag) break;
		}
		if(!flag) printf("NA\n");
	}
}