#include <iostream>
#include <utility>
#include <string>
#include <queue>
#include <map>

using namespace std;

typedef pair<string,int> P;

int main() {
	string str;
	char col[3]={'r','g','b'};

	while(cin>>str,str[0]!='0') {
		queue<P> que;
		map<string,bool> mp;

		mp[str]=true;
		que.push(P(str,0));
		int ans=-1;
		while(!que.empty()) {
			P p=que.front();
			que.pop();
			int len=p.first.length();
			bool f=true;
			for(int i=0;i<len-1;i++) {
				if(p.first[i]!=p.first[i+1]) {
					f=false;
					pair<int,int> tmp(p.first[i],p.first[i+1]);
					for(int j=0;j<3;j++) {
						if(p.first[i]!=col[j]&&p.first[i+1]!=col[j]) {
							p.first[i]=p.first[i+1]=col[j];
							break;
						}
					}
					if(mp[p.first]==false) {
						mp[p.first]=true;
						que.push(P(p.first,p.second+1));
					}
					p.first[i]=tmp.first;
					p.first[i+1]=tmp.second;
				}
			}
			if(f) {ans=p.second;break;}
		}
		if(ans==-1) {
			cout<<"NA"<<endl;
		}else {
			cout<<ans<<endl;
		}
	}
}