#include <iostream>
#include <map>
#include <deque>
#include <string>

using namespace std;

int main(void){
	string str;
	
	while(cin >> str && str != "0"){
		int ret = -1;
		map<string,bool> m;
		deque<pair<string,int> > q;
		string curstr,tmpstr;
		int curtime;
		
		q.push_back(make_pair(str,0));
		m[str] = true;
		while(!q.empty()){
			curstr = q.front().first;
			curtime = q.front().second;
			q.pop_front();
			
			//cout << curstr << endl;
			
			bool isended = true;
			
			for(int i=0;i<curstr.size()-1;i++){
				if(curstr[i] != curstr[i+1]) isended = false;
			}
			
			if(isended){
				ret = curtime;
				break;
			}
			
			tmpstr = curstr;
			
			for(int i=0;i<curstr.size()-1;i++){
				if((tmpstr[i] == 'b' && tmpstr[i+1] == 'g') ||
				(tmpstr[i] == 'g' && tmpstr[i+1] == 'b')){
					tmpstr[i] = 'r'; tmpstr[i+1] = 'r';
					//cout << tmpstr << endl;
					if(m[tmpstr] == false){
						m[tmpstr] = true;
						q.push_back(make_pair(tmpstr, curtime+1));
					}
					tmpstr = curstr;
				}else if((tmpstr[i] == 'r' && tmpstr[i+1] == 'g') ||
				(tmpstr[i] == 'g' && tmpstr[i+1] == 'r')){
					tmpstr[i] = 'b'; tmpstr[i+1] = 'b';
					if(m[tmpstr] == false){
						m[tmpstr] = true;
						q.push_back(make_pair(tmpstr, curtime+1));
					}
					tmpstr = curstr;
				}else if((tmpstr[i] == 'b' && tmpstr[i+1] == 'r') ||
				(tmpstr[i] == 'r' && tmpstr[i+1] == 'b')){
					tmpstr[i] = 'g'; tmpstr[i+1] = 'g';
					if(m[tmpstr] == false){
						m[tmpstr] = true;
						q.push_back(make_pair(tmpstr, curtime+1));
					}
					tmpstr = curstr;
				}
			}
		}
		if(ret == -1){
			cout << "NA" << endl;
		}else{
			cout << ret << endl;
		}
	}
}