#include <list>
#include <stdio.h>
#include <algorithm>
#include <string.h>

using namespace std;


typedef struct {
	char nood[11];
	int time;
} WORM;

unsigned int makeHash(char nood[])
{
	int i = 0;
	unsigned int ret = 0;
	while (nood[i] != -1){
		ret += nood[i];
		ret *= 3;
		i++;
	}
	
	return (ret);
}

int add_worm(list<WORM>* lstWorm, list<unsigned>& lstHash)
{
	WORM add;
	
	add.time = lstWorm->front().time + 1;
	
	int i = 0;
	while (lstWorm->front().nood[i + 1] != -1){
		if (lstWorm->front().nood[i] != lstWorm->front().nood[i + 1]){
			memcpy(add.nood, lstWorm->front().nood, 11);
			add.nood[i] = add.nood[i + 1] = 3 - (lstWorm->front().nood[i] + lstWorm->front().nood[i + 1]);
			if (find(lstHash.begin(), lstHash.end(), makeHash(add.nood)) == lstHash.end()){
				lstWorm->push_back(add);
				lstHash.push_back(makeHash(add.nood));
			}
		}
		i++;
	}
	
	return (0);
}

bool checkNood(char nood[])
{
	int i = 1;
	int d = nood[0];
	bool ret = true;
	
	while (nood[i] != -1){
		if (d != nood[i]){
			ret = false;
			break;
		}
		i++;
	}
	
	return (ret);
}

int main(void)
{
	list<unsigned int> lstHash;
	list<WORM> lstWorm;
	WORM add;
	
	while (1){
		lstHash.clear();
		lstWorm.clear();
		scanf("%s", add.nood);
		if (add.nood[0] == '0'){
			break;
		}
		int i = 0;
		while (add.nood[i] != '\0'){
			switch(add.nood[i]){
			  case 'r': add.nood[i] = 0; break;
			  case 'g': add.nood[i] = 1; break;
			  case 'b': add.nood[i] = 2; break;
			}
			i++;
		}
		add.nood[i] = -1;
		add.time = 0;
		
		lstWorm.push_back(add);
		lstHash.push_back(makeHash(add.nood));
		
		while (lstWorm.empty() == false && checkNood(lstWorm.front().nood) == false){
			add_worm(&lstWorm, lstHash);
			lstWorm.pop_front();
		}
		
		if (lstWorm.empty() == true){
			puts("NA");
		}
		else {
			printf("%d\n", lstWorm.front().time);
		}
	}
	
	return (0);
}