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

using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)
#define reps(i,n) for(int i=1;i<=n;i++)

class S{
	public:
	
	string a;
	int b;
	
	S(){}
	S(string a,int b):a(a),b(b){}
};


char nn[333][333];

int main(){
	
	nn['r']['g']='b';
	nn['g']['r']='b';
	
	nn['g']['b']='r';
	nn['b']['g']='r';
	
	nn['b']['r']='g';
	nn['r']['b']='g';
	
	while(1){
		string a;
		cin>>a;
		
		if(a=="0")break;
		
		map<string,int> ch;
		
		queue<S> que;
		que.push(S(a,0));
		
		while(1){
			if(que.empty()){
				cout<<"NA"<<endl;
				break;
			}
			
			S u = que.front();
			que.pop();
			
			if(ch[u.a]==1)continue;
			ch[u.a]=1;
			
			int flg=1;
			rep(i,u.a.size()-1){
				if(u.a[i] != u.a[i+1]){
					flg=0;
					break;
				}
			}
			if(flg==1){
				cout<<u.b<<endl;
				break;
			}
			
			rep(i,u.a.size()-1){
				if(u.a[i]!=u.a[i+1]){
					string b = u.a;
					b[i] = nn[u.a[i]][u.a[i+1]];
					b[i+1] = nn[u.a[i]][u.a[i+1]];
					
					que.push(S(b,u.b+1));
				}
			}
			
		}
	}
}