#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <math.h>
using namespace std;

bool OK(string in){
	for(int i = 0;i<in.size();i++){
		if (in[0] != in[i]) return false;
	}
	return true;
}

char ch(char a, char b){
	if (a != 'r' && b != 'r') return 'r';
	else if (a != 'g' && b != 'g') return 'g';
	else return 'b';
}

int main(){
	string in;
	while(cin >> in){
		if (in == "0") break;
		queue<string> que;
		que.push(in);
		vector<string> check(pow(3, in.size()));
		int n = 0, N = 0;
		while(true){
			int que_size = que.size();
			bool flag = false;
			if(que_size == 0){
				cout << "NA" << endl;
				break;
			}
			for(int i = 0;i<que_size;i++){
				string que_front = que.front();
				que.pop();
				if(OK(que_front)){
					cout << n << endl;
					flag = true;
					break;
				}
				for (int j = 0; j < que_front.size() - 1; j++) {
					if (que_front[j] == que_front[j + 1]) continue;
					string for_push = que_front;
					for_push[j] = for_push[j + 1] = ch(que_front[j], que_front[j + 1]);
					for (int k = 0; k <= N; k++){
						if (check[k] == for_push) break;
						if(k == N){
							N++;
							check[N] = for_push;
							que.push(for_push);
							break;
						}
					}
				}
			}
			if (flag) break;
			n++;
		}

	}
	return 0;
}