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

struct bug{
	string name;
	int tim;
};

int main()
{
	string worm;
	while(cin >> worm){
		if(worm == "0"){
			break;
		}
		map<string,int> memo;
		bug w;
		w.name = worm;
		w.tim = 0;
		queue<bug> que;
		que.push(w);
		bool fl = false;
		while(que.size()){
			bug tmp = que.front();
			que.pop();
			//êF»è
			bool flag = true;
			for(int i=0;i<tmp.name.size();i++){
				if(tmp.name[0] != tmp.name[i]){
					flag = false;
					break;
				}
			}
			if(flag){
				fl = true;
				cout << tmp.tim << endl;
				break;
			}
			//êxo½©»è
			if(memo.find(tmp.name) != memo.end())
				continue;
			else
				memo[tmp.name] = tmp.tim;

			//ÇÁ
			for(int i=0;i<tmp.name.size();i++){
				if(tmp.name[i] != tmp.name[i+1]){
					bug t = tmp;
					if((tmp.name[i] == 'r' && tmp.name[i+1] == 'g') || (tmp.name[i] == 'g' && tmp.name[i+1] == 'r') ){
						t.name[i] = 'b'; t.name[i+1] = 'b';
					}else if((tmp.name[i] == 'g' && tmp.name[i+1] == 'b') || (tmp.name[i] == 'b' && tmp.name[i+1] == 'g') ){
						t.name[i] = 'r'; t.name[i+1] = 'r';
					}else if((tmp.name[i] == 'b' && tmp.name[i+1] == 'r') || (tmp.name[i] == 'r' && tmp.name[i+1] == 'b') ){
						t.name[i] = 'g'; t.name[i+1] = 'g';
					}
					t.tim++;
					que.push(t);
				}
			}
		}
		if(!fl)
			cout << "NA" << endl;
	}
	return 0;
}