#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>
#include <sstream>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <numeric>
#include <cmath>
#include <climits>
#include <limits>
#include <cfloat>
#include <fstream>
using namespace std;

char change_color (char c1, char c2 )
{
	map<char, bool> used_color;
	used_color['r'] = false;
	used_color['g'] = false;
	used_color['b'] = false;

	used_color[c1] = true;
	used_color[c2] = true;

	map<char, bool>::iterator it = used_color.begin();
	for (; it != used_color.end(); ++it){
		if ( (*it).second == false ){
			return (*it).first;
		} // end if
	} // end for
} 
bool same_color (string s )
{
	int len = s.length();
	int n = (int)count (s.begin(), s.end(), s[0] );

	if (n == len ){
		return true;
	} // end if

	return false;
}	
	

int bfs (string str )
{
	int len = str.length();
	int i;

	queue <string> Q;
	string s = str;
	Q.push (s );
	set <string> S;
	multimap <string, string> D;

	while (!Q.empty() ){
		s = Q.front(); Q.pop();
//		cout << s << endl;
		if (same_color (s ) ){
			break;
		} // end if

		map<int, int> change_part;

		for (i = 0; i < len - 1; ++i){
			if (s[i] != s[i+1] ){
				change_part[i] = i+1;
			} // end if
		} // end for
		
		if (!change_part.empty() ){
			map<int, int>::iterator it = change_part.begin();
			for (; it != change_part.end(); ++it){
				string t = s;
				t[(*it).first] = change_color (s[(*it).first], s[(*it).second] );
				t[(*it).second] = change_color (s[(*it).first], s[(*it).second] );
				if (!S.count (t ) ){
					S.insert (t );
					Q.push (t );
					D.insert ( make_pair (t, s ) );
				} // end if
			} // end for
		} // end if
	} // end while

	if (Q.empty() && !same_color (s ) ){
		return -1;
	} // end if

	int res = 0;
	if (!D.empty() ){
		++res;
		multimap <string, string>::iterator it = D.begin();
		for (; it != D.end(); ++it){
			if ((*it).first == s ){
				 break;
			} // end if
		} // end for
		string from = (*it).second;
		while (from != str ){
			for (it = D.begin(); it != D.end(); ++it){
				if ( (*it).first == from ){
					from = (*it).second;
					++res;
					break;
				} // end if
			} // end for
		} // end while
	} // end if

	return res;	
}							 

int main()
{
//	cut here before submit 
//	freopen ("testcase.Mworm", "r", stdin );
	string str = "";
	int n;

	while (getline (cin, str ) ){
		int len = str.length();
		if (len == 1 && str[0] == '0'){
			break;
		} // end if
		int i;
		int res = 0;
		
		res = bfs (str );
		if (res == -1){
			cout << "NA" << endl;
		}else{
			cout << res << endl;	
		} // end if
	} // end loop
		
	return 0;
}