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

struct worm{
	char part[11];
	int dep;
	worm(){
		dep = 0;
	}
};

int main(){
	worm input;
	while (cin >> input.part, input.part[0] != '0'){
		int len;
		for (len = 0; input.part[len] != '\0'; len++){
			if (input.part[len] == 'r') input.part[len] = 0;
			else if (input.part[len] == 'g') input.part[len] = 1;
			else input.part[len] = 2;
		}
		queue<worm> q;
		q.push(input);
		worm q_c;
		bool memo[1000000] = {};
		while (1){
			bool color[3] = {};
			int sum1 = 0, sum2 = 0;
			int cnt_clr = 0;

			if (q.empty()){
				printf("NA\n");
				break;
			}

			q_c = q.front();

			for (int i = 0; i < len; i++){
				color[q_c.part[i]] = true;
			}
			for (int i = 0; i < 3; i++) if (color[i]) cnt_clr++;
			if (cnt_clr == 1){
				printf("%d\n", q_c.dep);
				break;
			}

			/*for (int i = 0; i < len; i++){
				printf("%d", q_c.part[i]);
				}*/
			for (int i = 0; i < len; i++){
				sum1 += q_c.part[i] * pow(3, i + 1);
				sum2 += q_c.part[i] * pow(3, len - i);
				//printf(" %d*%d^%d", q_c.part[i], 3, i + 1);
			}
			//printf(" =%d\n", sum1);
			if (memo[sum1]){
				q.pop();
				continue;
			}
			memo[sum1] = true;
			memo[sum2] = true;

			for (int i = 1; i < len; i++){
				if (q_c.part[i - 1] != q_c.part[i]){
					for (int j = 0; j < 3; j++) color[j] = false;

					color[q_c.part[i - 1]] = true;
					color[q_c.part[i]] = true;

					for (int j = 0; j < 3; j++){
						if (!color[j]){
							q_c.part[i - 1] = j;
							q_c.part[i] = j;
							q_c.dep++;
							q.push(q_c);
							q_c = q.front();
						}
					}
				}
			}
			q.pop();
		}
	}
	return 0;
}