#include <iostream>
#include <map>
#include <queue>
#include <string>
using namespace std;
#define rep2(x,from,to) for(int x=(from);x<(to);++(x))
#define rep(x,to) rep2(x,0,to)
bool same(string s) {
	rep(i,s.size()-1) {
		if(s[i+1] != s[i]) return false;
	}
	return true;
}
char change(char a, char b) {
	char c[3] = {'r', 'b', 'g'};
	rep(i,3) {
		if(a != c[i] && b != c[i]) return c[i];
	}
}
int bfs(string str) {
	queue<string> q;
	q.push(str);
	map<string, int> m;
	m[str] = 0;
	while(!q.empty()) {
		string s = q.front(); q.pop();
		if(same(s)) return m[s];
		rep(i,s.size()-1) {
			if(s[i+1] != s[i]) {
				string ns = s;
				ns[i+1] = ns[i] = change(ns[i+1],ns[i]);
				if(!m[ns]) {
					q.push(ns);
					m[ns] = m[s] + 1;
				}
			}
		}
	}
	return -1;
}
int main(){
	string s;
	while(cin >> s) {
		if(s =="0") break;
		int ret = bfs(s);
		if(ret == -1) cout << "NA" << endl;
		else cout << ret << endl;
	}
	return 0;
}