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

#define INF 100000000
typedef pair<string, int>P;

string S;

int main(){
	while(true){
	cin >> S;
	if(S == "0") return 0;
	queue<P>que;
	set<string>st;
	que.push(P(S, 0));
	int res = INF;
	while(!que.empty()){
		P p = que.front();
		que.pop();
		string s = p.first;
		if(st.find(s) != st.end()) continue;
		st.insert(s);
		bool foo = true;
		for(int i = 0; i < s.size(); i++){
			if(s[i] != s[0]) foo = false;
		}
		if(foo){
			res = p.second;
			break;
		}
		for(int i = 0; i < s.size() - 1; i++){
			if(s[i] != s[i + 1]){
				if(s[i] == 'g'&&s[i+1] == 'b'){
					s[i] = s[i+1] = 'r';
					que.push(P(s, p.second + 1));
					s[i] = 'g';s[i+1]='b';
				}
				if(s[i] == 'b'&&s[i+1] == 'g'){
					s[i] = s[i+1] = 'r';
					que.push(P(s, p.second + 1));
					s[i] = 'b';s[i+1]='g';
				}
				if(s[i] == 'r'&&s[i+1] == 'g'){
					s[i] = s[i+1] = 'b';
					que.push(P(s, p.second + 1));
					s[i] = 'r';s[i+1]='g';
				}
				if(s[i] == 'g'&&s[i+1] == 'r'){
					s[i] = s[i+1] = 'b';
					que.push(P(s, p.second + 1));
					s[i] = 'g';s[i+1]='r';
				}
				if(s[i] == 'r'&&s[i+1] == 'b'){
					s[i] = s[i+1] = 'g';
					que.push(P(s, p.second + 1));
					s[i] = 'r';s[i+1]='b';
				}
				if(s[i] == 'b'&&s[i+1] == 'r'){
					s[i] = s[i+1] = 'g';
					que.push(P(s, p.second + 1));
					s[i] = 'b';s[i+1]='r';
				}
			}
		}
	}
	if(res == INF) cout <<"NA" << endl;
	else cout << res << endl;
}
}

