#define	_USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <string>
#include <set>
using namespace std;
int main(){
	
	string s;
	while(cin>>s,s!="0"){
		set<string> seto;
		queue<string> q; 
		int count=0;
		bool f=false;
		q.push(s);
		seto.insert(s);
		while(!q.empty()){
			int k=q.size();
			while(k>0){
			string n=q.front();
					 f=true;
			for(int i=0;i<s.size();i++){
				if(n[0]!=n[i]){
					f=false;
					break;
				}
				
			}
				if(f)
					break;
			for(int i=0;i<s.size()-1;i++){
				string n=q.front();
				if(n[i]=='r'&&n[i+1]=='b'||n[i]=='b'&&n[i+1]=='r'){
						n[i]='g';
						n[i+1]='g';
				}
				else if(n[i]=='b'&&n[i+1]=='g'||n[i]=='g'&&n[i+1]=='b'){
						n[i]='r';
						n[i+1]='r';
				}
				else if(n[i]=='r'&&n[i+1]=='g'||n[i]=='g'&&n[i+1]=='r'){
						n[i]='b';
						n[i+1]='b';
				}
				set<string>::iterator a=seto.find(n);
				if(a==seto.end()){
					q.push(n);
					seto.insert(n);
					
				}
				}
				q.pop();
				k--;
			}
			if(f){
				
				break;
			}
			else{
				count++;
			}
		}
		if(f)
			cout<<count<<endl;
		else
			cout<<"NA"<<endl;
		
			
	}
	
	
}

	