#include <iostream>
#include <queue>
#include <map>
using namespace std;

char get(char a,char b){
	bool c[128]={0};
	c[a] = c[b] = true;
	if(!c['r'])return 'r';
	if(!c['g'])return 'g';
	if(!c['b'])return 'b';
}
bool same(string t){
	for(int i=0;i<t.size();i++)
		if(t[i] != t[0])return false;
	return true;
}
int main(){
	string str;
	while(cin >> str , str != "0"){
		queue<string> Q;
		map<string,int> done;
		done[str] = 0;
		Q.push(str);
		int ans = -1;
		while(Q.size()){
			string q = Q.front(); Q.pop();
			if(same(q)){ans = done[q];break;};
			for(int i=0;i<q.size()-1;i++){
				if(q[i] != q[i+1]){
					string t = q;
					t[i] = t[i+1] = get(q[i],q[i+1]);
					if(done.find(t) == done.end()){
						done[t] = done[q]+1;
						Q.push(t);
					}
				}
			}
		}
		if(~ans)cout << ans << endl;
		else cout << "NA" << endl;
	}
}