#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;

// c1, c2 テ」ツ??r', 'g', 'b', テ」ツ?凝」ツ?、(c1 != c2)テ」ツ?ョテ」ツ?ィテ」ツ??
// m[c1+c2] テ」ツ?ァ c1, c2 テ」ツ?ァテ」ツ?ェテ」ツ??r', 'g', 'b'テ」ツ?古ィツソツ氾」ツ?」テ」ツ?ヲテ」ツ?湘」ツつ?
map<int,char> m;

// テ・ツ?ィテゥツδィテ・ツ青古」ツ?佚ィツ可イテ」ツ?凝」ツ?ゥテ」ツ??」ツ??
bool isSameColor(const string& s){
	char c[3] = {'r','g','b'};
	for(int i = 0 ; i < 3 ; i++ ){
		int cnt = 0;
		for(int j=0 ; j < s.size() ; j++ ){
			if( s[j] == c[i] )
				cnt++;
		}
		if( cnt == s.size() )
			return true;
	}
	return false;
}

int solve(string s_ ){
	// memo[s] = true テ」ツ?ェテ」ツつ嘉ヲツ篠「テァツエツ「テヲツクツ暗」ツ?ソ
	map<string,bool> memo;
	// q.front().first テ」ツ?ッ ティツ卍ォテ」ツ?ョテァツ環カテヲツ??string) q.front().second テ」ツ?ッテヲツ可凝ヲツ閉ー(int)
	queue< pair<string,int> > q;
	
	// テ・ツ按敕ヲツ慊淌ァツ環カテヲツ?凝」ツつ津」ツつュテ」ツδ・テ」ツδシテ」ツ?ォテ・ツ?・テ」ツつ古」ツつ?
	pair<string,int> ini( s_ , 0  );
	q.push( ini );
	memo[s_] = true;
	
	// テ」ツつュテ」ツδ・テ」ツδシテ」ツ?古ァツゥツコテ」ツ?ォテ」ツ?ェテ」ツつ凝」ツ?セテ」ツ?ァテ」ツδォテ」ツδシテ」ツδ?
	while( !q.empty() ){
		// stirng s; テ」ツ?ッティツ卍ォテ」ツ?ョテァツ環カテヲツ?? int cnt; テ」ツ?ッテヲツ可凝ヲツ閉ー
		string s = q.front().first;
		int cnt = q.front().second;
		q.pop();
		
		// テ・ツ?ィテゥツδィテ・ツ青古」ツ?佚ィツ可イテ」ツ?ェテ」ツつ嘉ヲツ篠「テァツエツ「テァツオツづ、ツコツ?
		if( isSameColor(s) ){
			return cnt;
		}
		
		// テ」ツ?セテ」ツ??ヲツ篠「テァツエツ「テ」ツ?療」ツ?ヲテ」ツ??」ツ?ェテ」ツ??ヲツャツ。テ」ツ?ョテァツ環カテヲツ?凝」ツつ津」ツつュテ」ツδ・テ」ツδシテ」ツ?ォテ・ツ?・テ」ツつ古」ツつ?
		for(int i=1 ; i < s.size() ; i++ ){
			if( s[i-1] != s[i] ){
				char next_color = m[s[i-1]+s[i]];
				char c1 = s[i-1];
				char c2 = s[i];
				s[i-1] = s[i] = next_color;
				if( memo[s] != true ){
					memo[s] = true;
					pair<string,int> next;
					next.first = s;
					next.second = cnt + 1;
					q.push( next );
				}
				s[i-1] = c1;
				s[i] = c2;
			}
		}
	}
	return -1;
}

int main(){
	string s;
	m['r'+'g'] = 'b';
	m['g'+'b'] = 'r';
	m['b'+'r'] = 'g';
	
	while( cin >> s , s != "0" ){
		int ans = solve( s );
		if( ans == -1 )
			cout << "NA" << endl;
		else
			cout << ans << endl;
	}
}