#include<iostream>
#include<queue>
#include<cstdio>
#include<string>
#include<set>

#define R 114
#define G 103
#define B 98

using namespace std;

class DATA{
	public:
		DATA(string temp){			//ÌzñÆzñÌ·³ðnµÄ °Ä­¾³¢
			step = 0;
			arr = temp;
		}
		
		DATA(string temp, int step) :arr(temp), step(step) {}
		
		//I¹»èH
		int check(void){
			char t = arr[0];
			for(int i = 0; i < arr.size(); i++){
				if(arr[i] != t){
					return 0;
				}
			}
			return 1;
		}
		
		int step;		//Xebv(JÚ)
		string arr;	//rgbÌÀÑ
};

//¦
int ans = -1;

int main()
{
	string rgb;
	string temp;
	int i,j, len;
	int temp3;
	char g;
	
	
	for(;;){
		
		set<string> table;

		cin >> rgb;
		if(rgb == "0"){
			break;
		}
		len = rgb.size();
		ans = -1;
		queue<DATA> Q;
		
		DATA start(rgb,0);
		
		Q.push(start);
		while(!Q.empty()){
			//`FbN·éf[^ðæèo·
			DATA d = Q.front();
			Q.pop();
			
			if(table.count(d.arr)){
				continue;
			}
			
			table.insert(d.arr);
			
			//I¹
			if(d.check() == 1){
				ans = d.step;
				break;
			}
			
			//·×ÄÌp^[ÉÎµÄóÔJÚµAL[Éi[
			for(i = 0; i < len-1; i++){
				temp = d.arr;
				if(d.arr[i] != d.arr[i+1]){
					switch(d.arr[i]+d.arr[i+1]){
						case R+B:
							temp[i] = temp[i+1]= G;
							break;
						case R+G:
							temp[i] = temp[i+1] = B;
							break;
						case G+B:
							temp[i] = temp[i+1] = R;
					}
					
					DATA next(temp,d.step+1);
					Q.push(next);
				}
			}
		}
		if(ans == -1){
			cout << "NA" << endl;
		}
		else{
			cout << ans << endl;
		}
	}
}