#include<iostream>
#include<string>
#include<queue>
#include<cstring>
#include<set>
using namespace std;

//I¹Èç1ðÔ·
int samechar(string str);

//¯¶àÌª©Â©Á½ç1AÝÂ©ÈçÈ©Á½ç0ðÔ·
int samecheck(string str);

//strÌ[chari_1]Æ[chari_2]ÌFðÏ»³¹é
string exchange(string str, int chari_1, int chari_2);

set<string> samecheckset;

int main(){
	string input;
	while(cin >>input){
		if(input[0] == '0') break;
		
		samecheckset.clear();
		
		//cnt = oÍ·é¦([³) endflag = I¹ðª©Â©Á½ç1
		int cnt = 0, endflag = 0;
		
		//qu1 = ¡Ì[³Ìg qu2 = Ì[³Ìg
		queue<string> qu1, qu2;
		qu1.push(input);
		qu2.push("temp");
		while(!qu2.empty()){
			while(!qu2.empty()){
				qu2.pop();
			}
			while(!qu1.empty()){
				string temp = qu1.front();
				qu1.pop();
				
				//I¹ð¾Á½çbreak
				if(samechar(temp) == 1){
					endflag = 1;
					break;
				}
				
				//¯¶àÌªsamechecksetÉ©Â©Á½çcontinue
				if(samecheck(temp) == 1){
					continue;
				}
				
				//temp©çÏ»·é·×ÄÌFÌp^[ÌÂ\«ðqu2Éüêé
				for(int i = 0; i < temp.size() - 1; i++){
					if(temp[i] != temp[i + 1]){
						qu2.push(exchange(temp, i, i + 1));
					}
				}
			}
			
			if(endflag == 1){
				break;
			}
			
			//Ì[³ÉÚéÌÅAqu2Ìgð·×Äqu1ÉÚ·
			qu1 = qu2;
			
			//[³(b)ð1Ââ·
			cnt++;
		}
		if(endflag == 0){
			cout <<"NA" <<endl;
		} else{
			cout <<cnt <<endl;
		}
	}
}

string exchange(string str, int chari_1, int chari_2){
	if(str[chari_1] != 'r' && str[chari_2] != 'r'){
		str[chari_1] = 'r';
		str[chari_2] = 'r';
	} else if(str[chari_1] != 'g' && str[chari_2] != 'g'){
		str[chari_1] = 'g';
		str[chari_2] = 'g';
	} else if(str[chari_1] != 'b' && str[chari_2] != 'b'){
		str[chari_1] = 'b';
		str[chari_2] = 'b';
	}
	return str;
}

int samechar(string str){
	int ans = 1;
	char temp = str[0];
	for(int i = 1; i < str.size(); i++){
		if(temp != str[i]){
			ans = 0;
		}
	}
	return ans;
}

int samecheck(string str){
	if(samecheckset.find(str) == samecheckset.end()){
		samecheckset.insert(str);
		return 0;
	} else{
		return 1;
	}
}