#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;

// S¯¶F©Ç¤©
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 ÈçTõÏÝ
	map<string,bool> memo;
	// q.front().first Í ÌóÔ(string) q.front().second Íè(int)
	queue< pair<string,int> > q;
	
	// úóÔðL[Éüêé
	pair<string,int> ini( s_ , 0  );
	q.push( ini );
	memo[s_] = true;
	
	// L[ªóÉÈéÜÅ[v
	while( !q.empty() ){
		// stirng s; ÍÌóÔ, int cnt; Íè
		string s = q.front().first;
		int cnt = q.front().second;
		q.pop();
		
		// S¯¶FÈçTõI¹
		if( isSameColor(s) ){
			return cnt;
		}
		
		// Ü¾TõµÄ¢È¢ÌóÔðL[Éüêé
		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;
	}
}