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


#define Q_MAX 1000000
#define N 11

typedef struct {
	int cost;
	char color[N];
} QUEUE;


int main(void)
{
	char bug[N];
	int i, j;
	static QUEUE que[Q_MAX];
	int sq, eq;
	static char used[Q_MAX][N];
	
	do {
		int count = -1;
		scanf("%s", bug);
		
		if (bug[0] == '0') break;
		
		sq = 0;
		eq = 1;
		memset(que, 0, sizeof(que));
		memset(used, 0, sizeof(used));
		que[sq].cost = 0;
		strcpy(que[sq].color, bug);
		
		while (sq != eq){
			char color[N];
			int cost = que[sq].cost;
			
			strcpy(color, que[sq].color);
			sq = (sq + 1) % Q_MAX;
			
			if (strncmp(color, "rrrrrrrrrr", strlen(color)) == 0 ||
			strncmp(color, "gggggggggg", strlen(color)) == 0 ||
			strncmp(color, "bbbbbbbbbb", strlen(color)) == 0){
				count = (cost);
				break;
			}
			
			for (i = 0; color[i + 1] != '\0'; i++){
				if (color[i] != color[i + 1]){
					char buf[N];
					char check[3] = {1, 1, 1};
					char flag = 1;
					
					strcpy(buf, color);
					if (buf[i] == 'r' || buf[i + 1] == 'r') check[0] = 0;
					if (buf[i] == 'g' || buf[i + 1] == 'g') check[1] = 0;
					if (buf[i] == 'b' || buf[i + 1] == 'b') check[2] = 0;
					
					if (check[0] == 1){
						buf[i] = 'r';
						buf[i + 1] = 'r';
					}
					if (check[1] == 1){
						buf[i] = 'g';
						buf[i + 1] = 'g';
					}
					if (check[2] == 1){
						buf[i] = 'b';
						buf[i + 1] = 'b';
					}
					
					
					if (flag == 1){
						que[eq].cost = cost + 1;
						strcpy(que[eq].color, buf);
						strcpy(used[eq], buf);
						eq = (eq + 1) % Q_MAX;
					}
				}
			}
		}
		if (count != -1){
			printf("%d\n", count);
		}
		else {
			printf("NA\n");
		}
		
	} while (1);
	
	return (0);
}