#include <bits/stdc++.h>

using namespace std;

#define FOR(i, j, k) for(int i = j; i < k; ++i)
#define rep(i, j) FOR(i, 0, j)
#define Rrep(i, j) for(int i = j; i >= 0; --i)
#define INF (1 << 30)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<string, int> P;

string warm;

/*???????????????????????????*/
bool SameCol(string col) {
	rep(i, col.size() - 1) {
		if(col[i] != col[i + 1]) return false;
	}
	return true;
}
/*????????????*/
char ChangeCol(char a, char b) {
	if((a == 'r' && b == 'b') || (a == 'b' && b == 'r')) return 'g';
	else if((a == 'r' && b == 'g') || (a == 'g' && b == 'r')) return 'b';
	else if((a == 'b' && b == 'g') || (a == 'g' && b == 'b')) return 'r';
}

int solve(string s) {
	map<string, bool> m;	/*???????????\??¨*/
	queue<P> q;
	q.push(P(s, 0));

	while(!q.empty()) {
		P p = q.front(); q.pop();

		/*????????????*/
		if(m[p.first]) continue;
		m[p.first] = true;

		if(SameCol(p.first)) return p.second;
		string now = p.first;
		rep(i, now.size() - 1) {
			if(now[i] != now[i + 1]) {
				char tmp = ChangeCol(now[i], now[i + 1]);
				string tmp2 = now;
				tmp2[i] = tmp; tmp2[i + 1] = tmp;
				q.push(P(tmp2, p.second + 1));
			}
		}
	}
	return -1;
}

int main() {
	while(cin >> warm) {
		if(warm == "0") break;
		int ans = solve(warm);
		if(ans == -1) printf("NA\n");
		else printf("%d\n", ans);
	}
	return 0;
}