#include <iostream>
#include <utility>
#include <string>
#include <queue>
#include <set>
using namespace std;
#define P pair<string,int>
#define C(X)((X)=='r'?0:(X)=='b'?1:2)
int main() {
	string w;
	while(cin>>w,w!="0") {
		queue<P> q;
		set<string> s;
		q.push(P(w,0));
		s.insert(w);
		bool OK=false;
		while(!q.empty()) {
			P p=q.front();q.pop();
			bool ok=true;
			for(int i=1;i<p.first.size();i++) {
				if(p.first[i-1]!=p.first[i]) {
					ok=false;break;
				}
			}
			if(ok) {
				printf("%d\n",p.second);
				OK=true;break;
			}
			for(int i=1;i<p.first.size();i++) {
				if(p.first[i-1]!=p.first[i]) {
					string ns=p.first;
					bool chr[3]={0};
					chr[C(ns[i-1])]=true;
					chr[C(ns[i])]=true;
					for(int j=0;j<3;j++) {
						if(chr[j]==false) {
							ns[i-1]=ns[i]=(j==0?'r':j==1?'b':'g');
						}
					}
					if(s.find(ns)==s.end()) {
						q.push(P(ns,p.second+1));
						s.insert(ns);
					}
				}
			}
		}
		if(OK==false)printf("NA\n");
	}
}